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: Runtime Error

Solution code:
import numpy as np
def isprime(x):
  if x==1:
    return False
  if x==2:
    return True
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      return False
  return True

def like2017(x):
  return (isprime(x) and isprime((x+1)//2))


a=[like2017(i) for i in range(10**5+1)]

a_cum=np.cumsum(a)

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

Submission status: Runtime Error

Solution code:
Q = int(input())
lr = [tuple(map(int, input().split())) for i in range(Q)]


def primes(n):
    ret = []
    A = [i for i in range(2, n+1)]
    k = 0
    s = n**0.5
    while(k < s):
        ret.append(A[0])
        k = A[0]
        A = [x for x in A if x % k]
    ret += A
    return ret


prime = primes(10**5)

table = collections.defaultdict(int)
prime_s = set(prime)
t = [0]*(10**5 + 1)
for i in range(1, 10**5+1):
    if i in prime_s and (i+1)//2 in prime_s:
        t[i] = 1
for i in range(1, 10**5+1):
    t[i] = t[i] + t[i-1]

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

Submission status: Runtime Error

Solution code:
import bisect
def prime(n):
    max_=int(n**0.5)
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=max_:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes
Q=int(input())
arr=prime(100000)
likenum=[]
n=len(arr)
for i in range(n):
    lik=(arr[i]+1)//2
    x=bisect.bisect_left(arr,lik)
    if(x<n and arr[x]==(lik)):
        likenum.append(arr[i])
for i in range(Q):
    L,R=map(int,input().split())
    r=bisect.bisect_left(likenum,R)
    l=bisect.bisect_left(likenum,L)
    if(likenum[r]==R):
        r+=1
    print(r-l)

Submission status: Runtime Error

Solution code:
import numpy as np 
Q = int(input())

def prime(n):
    flag = True
    for i in range(2,int(np.sqrt(n)+1)):
        if (n%i)==0:
            flag = False
            break
    return flag

cnt = 0
cnts = [cnt,cnt,cnt]
b = [False,False,True]
for i in range(3,10003,2):
    flag = prime(i)
    b.extend([flag,False])
    if (b[int((i+1)/2)] and flag):
        cnt +=1
    cnts.extend([cnt,cnt])

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

Submission status: Runtime Error

Solution code:
import numpy as np 
Q = int(input())

def prime(n):
    flag = True
    for i in range(2,int(np.sqrt(n)+1)):
        if (n%i)==0:
            flag = False
            break
    return flag


cnt = 0
cnts = [cnt,cnt,cnt]
b = [False,False,True]
for i in range(3,10001,2):
    flag = prime(i)
    b.extend([flag,False])
    if (b[int((i+1)/2)] and flag):
        cnt +=1
    cnts.extend([cnt,cnt])

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

Submission status: Runtime Error

Solution code:
def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime
from bisect import bisect_left as bl
lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(input())
lis = set(lis)-{0}
lis = sorted(tuple(lis))
for _ in range(Q):
    l,r = map(int,input().split())
    t = bl(lis,l)
    tmp = 0
    if t == len(lis):print(tmp);continue
    while lis[t] <= r:
        tmp += 1
        t += 1
    print(tmp)

Submission status: Runtime Error

Solution code:
def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime
from bisect import bisect_left as bl
lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(input())
lis = set(lis)-{0}
lis = sorted(tuple(lis))
for _ in range(Q):
    l,r = map(int,input().split())
    t = bl(lis,l)
    tmp = 0
    while lis[t] <= r:
        tmp += 1
        t += 1
    print(tmp)

Submission status: Runtime Error

Solution code:
Q = int(input())
judge_arr = []
data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		if (i+1)/2 in prime_arr
			prime_arr.append(i)
			judge_arr.append(1)
		else:
			prime_arr.append(i)
			judge_arr.append(0)

#for n in range(len(prime_arr)):
	#if (prime_arr[n]+1)/2 in prime_arr:
		#judge_arr[n] = 1

def sumz(a,b):
	x = 0
	y = 0
	for n in range(len(prime_arr)):
		if prime_arr[n]<a:
			x = n
		if prime_arr[n]>b:
			y = n
			break
	return sum(judge_arr[x+1:y])

Submission status: Runtime Error

Solution code:
def sosu(x):
  for i in range(2,x**(1/2) + 1):
    if x % i == 0:
      return False
  return True

N = pow(10, 5)
lis = [0] * N
lis[1] = 1
for i in range(3,N+1):
  if i % 2 == 0:
    continue
  elif sosu(i) and lis[(N+1)//2-1] == 1:
    lis[i-1] = 1
ruiseki = [0]
total = 0
for i in range(N):
  total += lis[i]
  ruiseki.append(total)

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

Submission status: Runtime Error

Solution code:
4
13 13
7 11
7 11
2017 2017

Submission status: Runtime Error

Solution code:
q=int(input())
import math
import numpy as np
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
def is_is_prime(n):
    an=0
    if is_prime((n+1)//2)==True:
        if is_prime(n)==True:
            an=1
    return an
ko=[]
for i in range(1,10**5,2):
    ko.append(is_is_prime(i))

koko=np.cumsum(ko)

for i in range(q):
    l,r=map(int,input().split()) 
    if l==r:       
        if is_is_prime(l)==True:
            print(1)
        else:
            print(0)
    else:
        print(koko[r]-koko[l])

Submission status: Runtime Error

Solution code:
q=int(input())
import math
import numpy as np
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
def is_is_prime(n):
    an=0
    if is_prime((n+1)//2)==True:
        if is_prime(n)==True:
            an=1
    return an
ko=[]
print(is_is_prime(3))
for i in range(1,10**2,2):
    ko.append(is_is_prime(i))

koko=np.cumsum(ko)

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

Submission status: Runtime Error

Solution code:
# Q = int(input())

Qmax = 100_001
is_prime = [True] *  Qmax
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(Qmax ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, Qmax, i):
            is_prime[j] = False

# 1 ~ 10^5を先に計算する
cnt = 0
res = [0]*(10**5)
for i in range(10**5):
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt += 1
    res[i] = cnt


# 計算
Q = int(input())
for q in range(Q):
    li, ri = map(int, input().split())
    print(res[ri] - res[li - 1])

Submission status: Runtime Error

Solution code:
# Q = int(input())

def primes(n):
    ass = []
    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

prime_flag_list = primes(100_001)


# 1 ~ 10^5を先に計算する
list_flag = [False] * (100_001)
for n in range(1, 100_000 + 1, 2):
    if prime_flag_list[n] and prime_flag_list[(n + 1) // 2]:
        list_flag[n] = True

# 計算
Q = int(input())
for q in range(Q):
    li, ri = map(int, input().split())
    x = 0
    for i in range(li, ri+1, 2):
        if list_flag[i]:
            x += 1
    print(x)

Submission status: Runtime Error

Solution code:
#ABC084D 累積和
from itertools import accumulate
#エラトステネスの篩
def sieve(n: int) -> set: #返り値は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 i in range(Q):
    ans = sum[N[i][1]]-sum[N[i][0]-1] #累積和
    A.append(ans)
print('\n'.join(map(str, A)))

Submission status: Runtime Error

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 i in range(Q):
    ans = sum[N[i][1]]-sum[N[i][0]-1] #累積和
    A.append(ans)
print('\n'.join(map(str, A)))

Submission status: Runtime Error

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(100)

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

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


main()

Submission status: Runtime Error

Solution code:
import math
import bisect
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

prime=set([2])
for i in range(3,100001):
    if i%2!=0 and is_prime(i):
        prime.add(i)

sim_prime=[]
for p in prime:
    if (p+1)//2 in prime:
        sim_prime.append(p)
sim_prime.sort()


q=int(input())
ans_list=[]
for i in range(q):
    l,r=map(int,input().split())
    l_idx=bisect.bisect_left(sim_prime,l)
    r_idx=bisect.bisect_left(sim_prime,r)
    if sim_prime[r_idx]==r:
        r_idx+=1
    ans_list.append(r_idx-l_idx)

for g in range(len(ans_list)):
    print(ans_list[g])

Submission status: Runtime Error

Solution code:
def primes(n):
    primes = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            primes.append(i)
    return is_prime


Q = int(input())

ps = primes(10000)
like_numbers = [False] * 10001
for i in range(3, 10001, 2):
    if ps[i] and ps[(i + 1) // 2]:
        like_numbers[i] = True

like_numbers_cnt = [0] * 10001

for i in range(1, 10001):
    if like_numbers[i]:
        like_numbers_cnt[i] = like_numbers_cnt[i - 1] + 1
    else:
        like_numbers_cnt[i] = like_numbers_cnt[i - 1]

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

Submission status: Runtime Error

Solution code:
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(input())

'''
b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])
'''
a = [0] * (10**4+2)
for i in range(3, 10**4+1, 2):
    if is_p[i] and is_p[(i+1)//2]:
        a[i] = 1
for i in range(1, 10**4+1):
    a[i+1] += a[i]

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

Submission status: Runtime Error

Solution code:
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

# return p_list
 return is_p

q=int(input())

lim=10**2+1
is_p=eratosthenes(lim)

#print(is_p)

b=[0]
for i in range(1,lim+1):
 if is_p[i-1]==1 and is_p[i//2]==1:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])

#print(b)

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
import sympy

def main():
    N = int(input())
    M = 100000
    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
        return is_prime
    prime = sieve(M)
    alike = [0]
    for i in range(1,M+1,2):
        if (prime[i-1] and prime[(i+1)//2-1]):
            alike.append(alike[-1]+1)
        else:
            alike.append(alike[-1])
            
    for i in range(N):
        l,r = map(int,input().split())
        l = (l+1)//2
        r = (r+1)//2
        print(alike[r]-alike[l-1])
    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    prime_2007=[]
    j=0
    lr=[0]
    cnt=0

    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)

        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    
    for item in prime_list:
        if (item+1)//2 in prime_list:
            prime_2007.append(item)

    for item in prime_2007:
        lr+=[cnt]*(item - j-1)
        cnt+=1
        j=item
        lr.append(cnt)
    #print(prime_2007)
    #print(lr)
    #return prime_list
    return(lr)


lrlr=get_primenumber(10**5+10)

result=[]
n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    #l=min(l,len(lrlr)-1)
    #r=min(r,len(lrlr)-1)
    #print(l,r)
    #print(len(lrlr))

    result.append(lrlr[r]-lrlr[l-1])

for item in result:
    print(item)

Submission status: Runtime Error

Solution code:
import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    prime_2007=[]
    j=0
    lr=[0]
    cnt=0

    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)

        if (head_num+1)//2 in prime_list:
            prime_2007.append(head_num)
            lr+=[cnt]*(head_num - j-1)
            cnt+=1
            j=head_num
            lr.append(cnt)


        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    #print(prime_2007)
    #print(lr)
    #return prime_list
    return(lr)


lrlr=get_primenumber(10**5+1)

result=[]
n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    l=min(l,len(lrlr))
    r=min(r,len(lrlr))
    #print(l,r)
    #print(lrlr)

    result.append(lrlr[r]-lrlr[l-1])

for item in result:
    print(item)

Submission status: Runtime Error

Solution code:
import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    prime_2007=[]
    j=0
    lr=[0]
    cnt=0

    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)

        if (head_num+1)//2 in prime_list:
            prime_2007.append(head_num)
            lr+=[cnt]*(head_num - j-1)
            cnt+=1
            j=head_num
            lr.append(cnt)


        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    #print(prime_2007)
    #print(lr)
    #return prime_list
    return(lr)


lrlr=get_primenumber(10**5+1)

n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    l=min(l,len(lrlr))
    r=min(r,len(lrlr))
    #print(l,r)
    #print(lrlr)

    print(lrlr[r]-lrlr[l-1])

Submission status: Runtime Error

Solution code:
q=int(input())

like2017={}

# 自然数m以下の素数を返す
def prime_numbers(m):
    # 素数を保持するset
    primes = set()

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.add(n)
        n += 1
    result=set()
    result.add(2)
    for item in primes:
      if item!=2:
        if (item+1)//2 in primes:
          result.add(item)
    
    rl={}
    rl[0]=0
    for i in range(1,m+1):
      if i in result:
        rl[i]=rl[i-1]+1
      else:
        rl[i]=rl[i-1]
    return rl

rlrl=prime_numbers(100)

#print(rlrl)
        
for item in range(q):
  l,r=map(int,input().split())
  print(rlrl[r]-rlrl[l]+1)

Submission status: Runtime Error

Solution code:
q = int(input())
l = []
r = []
for i in range(q):
  x,y = map(int,input().split())
  l += [x]
  r += [y]


def is_2017(x):
  if x % 2 == 0:
    return False
  return is_p[x] && is_p[(x+1)//2]

def is_prime(x):
  if x == 1:
    return False
  i = 2
  while i * i <= x:
    if x % i == 0:
      return False
  return True
  
is_p = [False] * 100000
n_2017 = [0] * 100000

for i in range(1, 100000):
  is_p[i] = is_prime(i)

for i in range(1, 100000):
  if is_p[i]:
    n_2017[i] = n_2017[i-1] + 1

for i in range(q):
  print(n_2017[r]-n_2017[l-1])

Submission status: Runtime Error

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right
def eratosthenes(N):
    # 素数判定
    flag = True
    for i in range(2, int(N**0.5) + 1):
        if N % i == 0:
            flag = False
            break
    return flag

def make_prime_nums(N):
    # Nまでの素数のリストを作成
    prime_tf = [True for _ in range(N+1)]
    prime_tf[0] = False
    prime_tf[1] = False
    for i in range(N+1):
        if prime_tf[i]:
            if eratosthenes(i):
                for j in range(i*2, N+1, i):
                    prime_tf[j] = False
    primes = [i for i in range(N+1) if prime_tf[i]]
    return primes

def make_prime_new(L):
    new_primes = []
    for l in L:
        tmp = (l+1) // 2
        if eratosthenes(tmp):
            new_primes.append(l)
    return new_primes

primes = make_prime_nums(10**5)
primes = make_prime_new(primes)[1:]
# print(primes)
N = int(input())
for _ in range(N):
    l, r = map(int, input().split())
    l_idx = bisect_left(primes, l)
    r_idx = bisect_left(primes, r)
    if l == r and l_idx == r_idx and l == primes[l_idx]:
        print(1)
    else:
        print(r_idx - l_idx)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

def is_prime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

def make(n):
    ans=[]
    for i in range(2,n+1):
        if is_prime(i):
            ans.append(i)
    return ans

if __name__ == '__main__':
    Q=int(input())
    Queries=[list(map(int,input().split())) for i in range(Q)]
    upper=max(Queries,key=lambda x:x[1])
    p_list=make(upper)

    for l,r in Queries:
        count=0
        for i in range(l,r+1,2):
            if i in p_list:
                if (i+1)//2 in p_list:
                    count+=1
        print(count)

Submission status: Runtime Error

Solution code:
prime = [3, 5]
for i in range(13, 100001, 12):
  r = int(i**(1/2))
  p = 0
  for j in range(2, r+1):
    if i % j == 0:
      p = 1
      break
  a = (i+1)//2
  r = int(a**(1/2))
  for j in range(2, r+1):
    if a % j == 0:
      p = 1
      break
  if p == 0:
    prime.append(i)

Q = int(input())
for i in range(Q):
  L = list(map(int, input().split()))
  L[0] -= 1
  i = 0
  while L[0] >= prime[i]:
    i += 1
  j = 0
  while L[1] >= prime[j]:
    j += 1
  print(j-i)

Submission status: Runtime Error

Solution code:
#　n以下の整数の素数列挙（エラトステネスの篩）
#-------------------------------------------------------------------------
import numpy as np

def eratosthenes(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
#-------------------------------------------------------------------------
from itertools import accumulate

N = int(input())
L = [0] * N
R = [0] * N
A = eratosthenes(10*5)
B = [0] * 10*5
C = [0] * N

for i in range(10*5):
    if i in A:
        if (i+1)/2 in A:
            B[i] = 1

C = [0] + list(accumulate(B)) #out of rangeの回避

for i in range(N):
    L[i], R[i] = map(int, input().split())
for i in range(N):
    print(C[R[i]+1]-C[L[i]])

Submission status: Runtime Error

Solution code:
#　n以下の整数の素数列挙（エラトステネスの篩）
#-------------------------------------------------------------------------
import numpy as np

def eratosthenes(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
#-------------------------------------------------------------------------
from itertools import accumulate

N = int(input())
L = [0] * N
R = [0] * N
A = eratosthenes(10*5)
B = [0] * 10*5
C = [0] * N

for i in range(10*5):
    if i in A:
        if (i+1)/2 in A:
            B[i] = 1

C = [0] + list(accumulate(B)) #out of rangeの回避

for i in range(N):
    L[i], R[i] = map(int, input().split())
    print(C[R[i]+1]-C[L[i]])

Submission status: Runtime Error

Solution code:

M=pow(10,5)

prime_sieve=[-1 for i in range(M+1)]
prime_sieve[0]=1
prime_sieve[1]=1

primes=[]
for i in range(M+1):
  if prime_sieve[i]==-1:
    primes.append(i)
    for j in range(2,(M+1)//i+1):
      prime_sieve[i*j]=1
#print(prime_sieve)
rangesum=[0,0,0]
sum=0
for i in range(3,M+1):
  if prime_sieve[i]==-1:
    if prime_sieve[(i+1)//2]==-1:
       sum+=1
       #print(i,sum)
  rangesum.append(sum)

Q=int(input())
for i in range(Q):
  l,r=[int(x) for x in str(input()).split()]
  print(rangesum[r]-rangesum[l-1])

Submission status: Runtime Error

Solution code:

M=pow(10,2)

prime_sieve=[-1 for i in range(M+1)]
prime_sieve[0]=1
prime_sieve[1]=1

primes=[]
for i in range(M+1):
  if prime_sieve[i]==-1:
    primes.append(i)
    for j in range(2,(M+1)//i+1):
      prime_sieve[i*j]=1
#print(prime_sieve)
rangesum=[0,0,0]
sum=0
for i in range(3,M+1):
  if prime_sieve[i]==-1:
    if prime_sieve[(i+1)//2]==-1:
       sum+=1
       #print(i,sum)
  rangesum.append(sum)

Q=int(input())
for i in range(Q):
  l,r=[int(x) for x in str(input()).split()]
  print(rangesum[r]-rangesum[l-1])