Problem:


Score : 400 points

Problem Statement

We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Sample Input 1

1
3 7

Sample Output 1

2

3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.

5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.

7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.

Thus, the response to the first query should be 2.

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

6
1 53
13 91
37 55
19 51
73 91
13 49

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Accepted

Solution code:
def prime_list(n):
    # n以下の自然数で素数か否かのリストを作成
    ans = [True for _ in range(n+1)]
    ans[0] = False
    ans[1] = False
    for i in range(2,n+1):
        if ans[i]:
            for j in range(2*i,n+1,i):
                ans[j] = False
    return ans

prime = prime_list(10**5)
like = [0 for i in range(10**5+1)]
for i in range(3,10**5+1,2):
    if prime[i] and prime[(i+1)//2]:
        like[i] = 1
for i in range(1,10**5+1):
    like[i] += like[i-1]

q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(like[r]-like[l-1])

Submission status: Accepted

Solution code:
from math import sqrt,ceil
n = int(int(1e5))

def prime():
    d = [True] * (n+1)
    d[0] = False
    d[1] = False
    for i in range(2,ceil(sqrt(n+1))):
        if d[i] == True:
            j = 2
            while i * j <= n:
                d[i*j] = False
                j += 1
    return d
d = prime()
#print(d)
cum = [0] * (n + 1)
for i in range(1,n+1):
    cum[i] = cum[i-1]
    if i % 2 == 1:
        if d[i] == True and d[(i+1)//2] == True:
            cum[i] += 1
#print(cum)
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(cum[r] - cum[l-1])

Submission status: Accepted

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
Q = int(input())
ans = [0] * (10**5+1)
prime = primes(10**5)
for i in range(1,10**5+1):
    if prime[i] == 1 and prime[(i+1)//2] == 1:
        ans[i] = ans[i-1] + 1
        continue
    ans[i] = ans[i-1]
for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])

Submission status: Accepted

Solution code:
import math
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
Q = int(input())
ans = [0] * (10**5+1)
prime = [0] * (10**5+1)
for i in range(1,10**5+1):
    if is_prime(i):
        prime[i] = 1
        if prime[(i+1)//2] == 1:
            ans[i] = ans[i-1] + 1
            continue
    ans[i] = ans[i-1]
disp_ans = 0
for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math


def is_sosu(n):

    if n == 2:
        return True

    if n < 2 or n % 2 == 0:
        return False

    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False

    return True


def similar_to_2017(n):
    if is_sosu(n) and is_sosu((n + 1) / 2):
        return True

    return False


def main():
    q = int(input())
    in_target = [tuple(map(int, input().split())) for i in range(q)]

    similar_to_2017s = {}
    for i in range(1, 100001, 2):
        if similar_to_2017(i):
            similar_to_2017s[i] = 1 + similar_to_2017s.get(i - 2, 0)
        else:
            similar_to_2017s[i] = similar_to_2017s.get(i - 2, 0)

    for target in in_target:
        cnt = similar_to_2017s.get(target[1], 0) - similar_to_2017s.get(target[0] - 2, 0)

        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=10**5
is_prime=[True]*(n+1)
is_prime[0]=False
is_prime[1]=False
for i in range(2,int(n**0.5)+1):
  if not is_prime[i]:
    continue
  for j in range(i*2,n+1,i):
    is_prime[j]=False
A=[0]*n
def f(x):
  return is_prime[x] and is_prime[(x+1)//2]

for i in range(3,n,2):
  if f(i):
    A[i]=A[i-2]+1
  else:
    A[i]=A[i-2]
A=[0]+A
q=int(input())
for _ in range(q):
  l,r=map(int,input().split())
  print(A[r+1]-A[l-1])

Submission status: Accepted

Solution code:
q=int(input())
part=[list(map(int,input().split())) for i in range(q)]

cumsum=[0]*(10**5+1)

plst=[1]*(10**5+1)

plst[0]=0
plst[1]=0

i=2

while i*i<=10**5:
    for j in range(2,10**5//i+1):
        plst[i*j]=0
    
    i+=1
    while plst[i]==0:
        i+=1

for i in range(2,10**5+1):
    if plst[i]==1 and plst[(i+1)//2]==1:
        cumsum[i]=cumsum[i-1]+1
    else:
        cumsum[i]=cumsum[i-1]

for l,r in part:
    print(cumsum[r]-cumsum[l-1])

Submission status: Accepted

Solution code:
flg = [1] * (10**5+1)
flg[0], flg[1] = 0, 0
for i in range(2,10**5+1):
	if flg[i] == 1:
		for j in range(2*i, 10**5+1, i):
			flg[j] = 0

cnt = [0,0]
tmp = 0
for i in range(2,10**5+1):
	if flg[i] == 1:
		if flg[(i+1)//2] == 1:
			tmp += 1
			cnt.append(tmp)
		else:
			cnt.append(tmp)
	else:
		cnt.append(tmp)

Q = int(input())
ans = []

for _ in range(Q):
	tl,tr = map(int, input().split())
	ans.append(cnt[tr] - cnt[tl-1])

for a in ans:
	print(a)

Submission status: Accepted

Solution code:
import math
Q=int(input())

def prime_judge(n):  
  if n == 2:
    return True
  if n < 2 or n % 2 == 0:
    return False
  for i in range(3, int(math.sqrt(n)) + 1, 2):
    if n % i == 0:
      return False
  return True

dic={}
dic[1]=0
for i in range(3,10**5+1,2):
  if prime_judge(i) and prime_judge((i+1)//2):
    dic[i]=dic[i-2]+1
  else:
    dic[i]=dic[i-2]
    
for q in range(Q):
  x,y=map(int,input().split())
  if x==y:
    if prime_judge(x) and prime_judge((x+1)//2):
      print(1)
    else:
      print(0)
  else:
    if prime_judge(x) and prime_judge((x+1)//2):
      print(dic[y]-dic[x]+1)
    else:
      print(dic[y]-dic[x])

Submission status: Accepted

Solution code:
from math import ceil,sqrt
from bisect import bisect_right, bisect_left

def trial_division(n):  
  if n == 2:
    return True
  if n < 2 or n % 2 == 0:
    return False
  for i in range(3, int(ceil(sqrt(n))) + 1, 2):
    if n % i == 0:
      return False
  return True

import sys
input = lambda: sys.stdin.readline().rstrip()
q = int(input())

primes = [i for i in range(10**5+10) if trial_division(i)]  
p2017 = []
for i in range(len(primes)-1):
  if trial_division((primes[i]+1)//2):
    p2017.append(primes[i])
    
for i in range(q):
  l,r = map(int,input().split())  
  print(bisect_right(p2017,r) - bisect_left(p2017,l))

Submission status: Accepted

Solution code:
import math

def is_prime(n):
    if n==1 :
        return False

    for k in range(2,int(math.sqrt(n))+1):
        if n%k==0:
            return False

    return True

count = [0]
buf = 0
for i in range(1, 10**5 + 2):
    if i % 2 == 0:
        count.append(buf)
        continue

    hantei1 = is_prime(i)
    hantei2 = is_prime((i+1)//2)

    if hantei1 and hantei2:
        buf += 1

    count.append(buf)

q = int(input())

for i in range(q):
    l,r = map(int,input().split())
    print(count[r]-count[l-1])

Submission status: Accepted

Solution code:
dp = [[0 for _ in range(5 * (10 ** 4))] for _ in range(3)]
dp[1][0], dp[0][1], dp[1][1] = 1, 1, 1
for i in range(5, 10 ** 5, 2):
    c = 0
    if (i % 5 == 0 and i != 5) or (i % 3 == 0 and i != 3):
        c = 1
    if c == 0:
        for j in range(2, int(i ** (1 / 2)) + 1):
            if i % j == 0:
                c = 1
                break
    if c == 0:
        dp[0][i // 2] = 1
for i in range(5, 10 ** 5, 2):
    c = (i + 1) // 2
    if dp[0][c // 2] == 1 and c % 2 == 1:
        dp[1][i // 2] = 1
for i in range(1, 5 * (10 ** 4)):
    if dp[0][i] == dp[1][i] == 1:
        dp[2][i] = dp[2][i - 1] + 1
    else:
        dp[2][i] = dp[2][i - 1]

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    l, r = l // 2 - 1, r // 2
    if l == -1:
        l = 0
    print(dp[2][r] - dp[2][l])

Submission status: Accepted

Solution code:
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]

n = 10 ** 5 + 2
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, n + 1):
    if not is_prime[i]:
        continue

    for j in range(2 * i, n + 1, i):
        is_prime[j] = False

like = [False] * (n + 1)
for i in range(n):
    like[i] = is_prime[i] and is_prime[(i + 1) // 2]

cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i + 1] = cumsum[i] + like[i]

for l, r in X:
    print(cumsum[r + 1] - cumsum[l])

Submission status: Accepted

Solution code:
#ABC084D 累積和
from itertools import accumulate
#エラトステネスの篩
def sieve(n: int) -> set: #返り値はset
    if n < 2:
        return set()
    
    num = [True]*n
    num[0] = num[1] = False
    for i in range(3,int(n**0.5)+1,2):
        if num[i]:
            num[i * i:: 2 * i] = [False] * ((n - i ** 2 - 1) // (2 * i) + 1)
    return {2}|{i for i in range(3,n,2) if num[i]}

primelist = sieve(10**5+1)
Q = int(input())
N = []
A = []
for i in range(Q):
    num = list(map(int, input().split()))
    N.append(num)
    
#prime = list(set(sieve(r))-set(sieve(l)))#重複がないlist同士の引き算
    
_2017_like = [1 if i in primelist and (i + 1) // 2 in primelist else 0 for i in range(10**5+1)]#2017likeな数のindexが求まる
sum = list(accumulate(_2017_like)) #ある数までの解の個数
for j in range(Q):
    ans = sum[N[j][1]]-sum[N[j][0]-1] #累積和
    A.append(ans)
print('\n'.join(map(str, A)))

Submission status: Accepted

Solution code:
import math
import numpy

def is_prime(n):
    if (n==1):
        return 0
    if (n==2):
        return 1
    for i in range(3,int(math.sqrt(n))+1,2):
        if (n % i == 0):
            return 0
    return 1

prime = [0]*(10**5+1)
for i in range(1,10**5+1,2):
    prime[i] = is_prime(i)
prime[2] = 1

q = int(input())
li = [0]*(10**5+1)
for i in range(1,10**5+1):
    if (i%2 == 1):
        if (prime[i] and prime[int((i+1)/2)]):
            li[i] = 1

com = numpy.cumsum(li)
for _ in range(q):
    l,r = [int(x) for x in input().split()]
    print(com[r]-com[l-1])

Submission status: Accepted

Solution code:
INFTY = 10**5+1
P = [1 for _ in range(INFTY)]
P[0]=P[1]=0
for i in range(2,int(INFTY**0.5)+1):
    for j in range(i*i,INFTY,i):
        P[j] = 0
R = [0 for _ in range(INFTY)]
for i in range(INFTY):
    if i%2==1:
        if P[i]==1 and P[(i+1)//2]==1:
            R[i] = 1
A = [0 for _ in range(INFTY+1)]
for i in range(INFTY):
    A[i+1] = A[i]+R[i]
Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    print(A[r+1]-A[l])

Submission status: Accepted

Solution code:
from math import sqrt
def is_prime(n) :
    if (n <= 1) :
        return False
    if (n <= 3) :
        return True
    # check 6k+0,2,3,4
    if (n % 2 == 0 or n % 3 == 0) :
        return False
    i = 5
    while(i * i <= n) :
        # check 6k+1, 6k+5
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

nums = [0] * (100001)
for i in range(1, 100001):
    if is_prime(i) and is_prime( (i + 1) // 2):
        nums[i] = 1
for i in range(1, 100001):
    nums[i] += nums[i-1]

Q = int(input())
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print(nums[r] - nums[l-1])

Submission status: Accepted

Solution code:
M=10**6
p=[1]*M
p[0]=p[1]=0
for i in range(2,10**5+1):
    if p[i]:
        for j in range(i*i,M,i):
            p[j]=0
C=[0]*M
for i in range(2,M):
    if p[i] and p[(i+1)//2]:
        C[i]=C[i-1]+1
    else:
        C[i]=C[i-1]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(C[r]-C[l-1])

Submission status: Accepted

Solution code:
M=10**6
p=[1]*M
p[0]=p[1]=0
for i in range(2,4*10**4):
    if p[i]:
        for j in range(i*i,M,i):
            p[j]=0
C=[0]*M
for i in range(2,M):
    if p[i] and p[(i+1)//2]:
        C[i]=C[i-1]+1
    else:
        C[i]=C[i-1]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(C[r]-C[l-1])

Submission status: Accepted

Solution code:
import numpy as np
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

U = 10**5 * 1
is_prime = np.ones(U, dtype='bool')
is_prime[0:2] = False
for i in range(2, U):
    if i * i > 10**5:
        break
    if is_prime[i]:
        is_prime[i * 2::i] = False

like_2017 = np.zeros(U, dtype='bool')
for i in range(1, U):
    if 2 * i > U:
        break
    if is_prime[i] and is_prime[i * 2 - 1]:
        like_2017[i * 2 - 1] = True
cumsum = like_2017.cumsum()

for l, r in lr:
    print(cumsum[r] - cumsum[l - 1])

Submission status: Accepted

Solution code:
import numpy as np
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

is_prime = np.zeros(10**5 + 1, dtype='bool')
for i in range(2, 10**5 + 1):
    if not is_prime[i]:
        for j in range(2, int(np.sqrt(i) + 1)):
            if i % j == 0:
                break
        else:
            is_prime[i] = True
            # is_prime[::i] = True
# print(is_prime[:10])

like_2017 = np.zeros(10**5 + 1, dtype='bool')
for i in range(1, 10**5 + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        like_2017[i] = True
# print(like_2017)
# print(like_2017.cumsum())
cumsum = like_2017.cumsum()

for l, r in lr:
    print(cumsum[r] - cumsum[l - 1])

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
import bisect as bi
from operator import mul
from functools import reduce
import math
from itertools import accumulate

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def prime(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return is_prime

def main():
    q = int(input())
    is_prime = prime(10**5)

    def p(total, x):
        return total + (1 if is_prime[x] and is_prime[(x+1)//2] else 0)

    cumsum = list(accumulate(range(10**5), p))
    for l, r in readlines(q):
        print(cumsum[r] - cumsum[l-1])


main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc084/tasks/abc084_d
from bisect import bisect_left, bisect_right
q = int(input())
queries = []
MAX = 0
for _ in range(q):
    l, r = map(int, input().split())
    queries.append((l, r))
    MAX = max([MAX, l, r])
from datetime import datetime
s = datetime.now()
def eratos(x):
    dp = [True] * (x + 1)
    dp[0] = dp[1] = False
    i = 2
    sqrt = x ** 0.5
    while i <= sqrt:
        if dp[i]:
            for j in range(i ** 2, x + 1, i):
                dp[j] = False
        i += 1
    primes = []
    for i in range(len(dp)):
        if dp[i]:
            primes.append(i)
    return primes, dp

primes, dp = eratos(MAX)
sub_prims = []
for p in primes:
    x = (p + 1) // 2
    if dp[x]:
        sub_prims.append(p)

for l, r in queries:
    left = bisect_left(sub_prims, l)
    right = bisect_left(sub_prims, r + 1)
    print(right - left)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

#引数nが素数かどうかを判定
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


## エラトステネス のふるい(n以下の素数全列挙)
# O(NloglogN)
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return table,is_prime

def main():
    Q = INT()
    N = 10**5
    table,is_prime = sieve(N)
    is_like_number = [0]*(N+1)
    from itertools import accumulate
    for prime in table:
        if prime == 2:
            continue
        if is_prime[(prime+1)//2-1]:
            is_like_number[prime] = 1
    accum_like_number = list(accumulate(is_like_number))
    for _ in range(Q):
        l,r = MAP()
        print(accum_like_number[r]-accum_like_number[l-1])

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
q = int(input())
l = []
for i in range(q):
    l.append(list(map(int,input().split())))
prime = [2]
A = 10+10**5
for L in range(3, A, 2):
    for L2 in prime:
        if L % L2 == 0:
            break
    else:
        prime.append(L)
like=[]
for num in prime:
    if (num+1)//2 in prime:
        like.append(num)
import bisect
for tmp in l:
    indl = bisect.bisect_left(like,tmp[0])
    indr = bisect.bisect_right(like,tmp[1])
    print(indr-indl)

Submission status: Accepted

Solution code:
MAX = 10**5
is_prime = [True for i in range(MAX + 1)]
is_prime[0], is_prime[1] = False, False 
i = 2
while i ** 2 <= MAX:
    if is_prime[i]:
        j = 2 * i
        while j <= MAX:
            is_prime[j] = False
            j += i
    i += 1

a = [0 for i in range(MAX)]
for i in range(MAX + 1):
    if i % 2 == 0:
        continue
    if is_prime[i] and is_prime[(i + 1) // 2]:
        a[i] = 1

s = [0 for i in range(MAX + 2)]
for i in range(MAX):
    s[i + 1] = s[i] + a[i]
    
Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    print(s[r + 1] - s[l])

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = lambda: sys.stdin.readline().rstrip()

MAX = 10 ** 5

def eratosthenes(n):
    is_prime = [1] * (n+1)
    is_prime[0] = 0
    is_prime[1] = 0

    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = 0
    return is_prime        


Q = int(input())

is_prime = eratosthenes(MAX)

a = [0] * (MAX+1)
for i in range(MAX+1):
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] = 1
s = [0] + a
s = list(accumulate(s))

for i in range(Q):
    l, r = map(int, input().split())
    print(s[r+1]-s[l])

Submission status: Accepted

Solution code:
import math
Q=int(input())
A=[list(map(int,input().split())) for i in range(Q)]
B,C=zip(*A)
a=max(max(B),max(C))

def get_primenumber(n):
  prime=[]
  limit=math.sqrt(n)
  data=[i+1 for i in range(1, n)]
  while True:
    p=data[0]
    if limit<=p:
      return prime+data
    prime.append(p)
    data=[e for e in data if e % p != 0]
        
X=get_primenumber(a)
P=[False]*(a+1)
L=[False]*(a+1)
for i in X:
  P[i]=True
for i in X:
  if P[(i+1)//2]:
    L[i]=True
C=[]
c=0
for i in range(a+1):
  if L[i]:
    c+=1
  C.append(c)
for s,t in A:
  print(C[t]-C[s-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
 
##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力
 
# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと
 
##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順
 
# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順
 
##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
inf = float('inf')
mod = 1000000007
 
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def main():
    Q = inputInt()
    
    total = 0
    lists = [0,0]
    for i in range(2,10**5+1):
        if i % 2 == 0:
            lists.append(total)
            continue
            
        if is_prime(i) == True and is_prime((i+1)//2) == True:
            total += 1
        lists.append(total)
        
    #print(lists)
    for i in range(Q):
        l,r = inputMap()
        #print("{} {}".format(lists[r], lists[l]))
        print(lists[r] - lists[l-1])
    
def is_prime(n): 
    i = 2
    while i * i <=n:
        if n % i == 0:
            return False
        i += 1
    return True
     
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y
         
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import math
n = 100000
integer = [i for i in range(2,n+1)]
prime = set()
while integer[0] <= math.sqrt(n):
    p = integer[0] 
    prime.add(p)
    integer = [i for i in integer if i % p != 0]
prime = prime | set(integer)
like = set()
likesum = [0]*(n+1)
for i in prime:
    if (i+1)//2 in prime:
        like.add(i)
for i in range(n):
    if i in like:
        likesum[i+1] = likesum[i] + 1
    else:
        likesum[i+1] = likesum[i]    
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(likesum[r+1]-likesum[l])

Submission status: Accepted

Solution code:
import math
n = 100000
integer = [i for i in range(2,n+1)]
prime = []
while integer[0] <= math.sqrt(n):
    p = integer[0] 
    prime.append(p)
    integer = [i for i in integer if i % p != 0]
prime = prime + integer
like = []
likesum = [0]*(n+1)
for i in range(len(prime)):
    if (prime[i]+1)//2 in prime:
        like.append(prime[i])
for i in range(n):
    if i in like:
        likesum[i+1] = likesum[i] + 1
    else:
        likesum[i+1] = likesum[i]    
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(likesum[r+1]-likesum[l])

Submission status: Accepted

Solution code:
#素数かどうか

import numpy as np
def list_primes(N):
    is_prime = np.ones(N+1, dtype=np.bool)
    # iが素数ならTrue，素数でないならFalse
    is_prime[0] = False
    is_prime[1] = False
    for i in range(N+1):
        if is_prime[i]:
            is_prime[2*i::i] = False
            # iの倍数の部分をスライスで選択して「素数でない」に設定
    #return is_prime.nonzero()
    return is_prime
    # is_primeがTrueになるもののindexのarray
    
N = 10**5
is_prime = list_primes(N)


#2017ににた数のリストの作成
def solve(is_prime):
    ans = []
    for i in range(len(is_prime)-1):
        if i % 2 == 1:
            if is_prime[i] and is_prime[(i+1)//2]:
                ans.append(i)
    return ans

like2017 = solve(is_prime)



#二分探索
def nibu_right(a,A): #a in A(sorted)
    if a<A[0]:return 0
    elif A[-1]<=a:return len(A)
    else:
        mi = 0
        ma = len(A)-1
        while ma-mi>1:
            mid = (ma+mi)//2
            if a > A[mid]:
                mi = mid
            else:
                ma = mid
        # A[mi]<a  a<=A[ma]
        if A[ma] == a:return ma+1
        else: return ma

def nibu_left(a,A): #a in A(sorted)
    if a<=A[0]:return 0
    elif A[-1]<a:return len(A)
    else:
        mi = 0
        ma = len(A)-1
        while ma-mi>1:
            mid = (ma+mi)//2
            if a < A[mid]:
                ma = mid
            else:
                mi = mid
        # A[mi]<=a  a<A[ma]
        if A[mi] == a:return mi
        else: return mi+1






Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    l_index = nibu_left(l,like2017)
    r_index = nibu_right(r,like2017)
    print(r_index - l_index)

Submission status: Accepted

Solution code:
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

def sosuu(num):
    Result = True
    for i in range(2, int(num**(1/2))+1):
        if num%i==0:
            Result = False
            break
    return Result #素数なら True

checker = [1 for i in range(10**5+1)]
checker[0] = 0
checker[1] = 0
for i in range(2, 10**5+1):
    if checker[i]:
        if sosuu(i):
            j = 2
            while i*j <= 10**5:
                checker[i*j] = 0
                j += 1
result = [0]
j = 0
for i in range(1, len(checker)):
    if checker[i] and checker[(i+1)//2]:
        j += 1
    result.append(j)

for l, r in lr:
    print(result[r]-result[l-1])