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: Time Limit Exceeded

Solution code:
prime=[3,5,13,37,61,73,157,193,277,313,397,421,457,541,613,661,673,733,757,877,997,1093,1153,1201,1213,1237,1321,1381,1453,1621,1657,1753,1873,1933,1993,2017,2137,2341,2473,2557,2593,2797,2857,2917,3061,3217,3253,3313,3517,3733,4021,4057,4177,4261,4273,4357,4441,4561,4621,4933,5077,5101,5113,5233,5413,5437,5581,5701,6037,6073,6121,6133,6217,6337,6361,6373,6637,6661,6781,6997,7057,7213,7393,7417,7477,7537,7753,7933,8053,8101,8221,8317,8353,8461,8521,8677,8713,8893,9013,9133,9181,9241,9277,9601,9661,9721,9817,9901,9973,10333,10357,10453,10837,10861,10957,11113,11161,11317,11497,11677,11701,12073,12157,12241,12301,12421,12433,12457,12541,12553,12601,12721,12757,12841,12853,13093,13381,13417,13681,13921,13933,14437,14593,14737,14821,15013,15073,15121,15241,15277,15361,15373,15733,15901,16033,16333,16381,16417,16573,16633,16657,16921,17041,17053,17077,17257,17293,17377,17881,18013,18097,18133,18181,18217,18253,18301,18313,18397,18481,18553,18637,18793,19237,19441,19477,19717,19801,19813,19861,20353,20533,20641,20857,21001,21061,21193,21277,21313,21577,21661,21673,21817,22093,22501,22573,22621,22993,23053,23173,23557,23677,23773,23917,24097,24421,24481,24781,24841,25033,25153,25237,25561,25657,25933,26017,26293,26317,26437,26497,26821,26833,26881,26953,27073,27253,27337,27361,27457,27997,28057,28297,28393,28813,28837,28921,29101,29473,29641,30181,30241,30517,30553,30577,30637,30661,30697,30781,30853,31081,31237,31321,31333,31357,31477,31573,31873,31981,32173,32377,32497,32533,32833,33037,33301,33457,33493,33757,33961,34057,34213,34273,34381,34513,34897,34981,35317,35521,35677,35977,36097,36241,36433,36457,36793,36877,36901,36913,37273,37321,37357,37573,37717,37957,38281,38461,38833,38953,38977,39217,39373,39397,39733,40093,40177,40213,40693,40813,41017,41221,41281,41413,41617,41893,42061,42337,42373,42793,42961,43117,43177,43201,43321,43573,43597,43633,43717,44053,44101,44221,44257,44293,44893,45061,45337,45433,45481,45553,45613,45841,46021,46141,46261,46861,46993,47017,47161,47353,47521,47533,47653,47713,47737,47797,47857,48121,48193,48337,48673,48757,48781,49033,49261,49393,49417,49597,49681,49957,50221,50341,50377,50821,50893,51157,51217,51241,51481,51517,51637,52057,52081,52237,52321,52453,52501,52813,52861,52957,53077,53113,53281,53401,53917,54121,54133,54181,54217,54421,54517,54541,54673,54721,54973,55057,55381,55501,55633,55837,55921,55933,56053,56101,56113,56197,56401,56437,56701,56773,56821,56857,56893,57073,57097,57193,57241,57373,57457,57853,58153,58417,58441,58537,58573,58693,59053,59197,59221,59281,59341,59833,60217,60337,60373,60637,60733,60937,61057,61153,61261,61297,61561,61657,61681,61717,61861,62137,62473,62497,62533,62653,62773,63313,63397,63541,63697,63781,63913,64153,64237,64381,64513,64717,65173,65293,65413,65437,65497,65557,65677,65881,66301,66361,66601,66697,66853,66973,67057,67153,67273,67477,67537,67741,67777,67933,67993,68113,68281,68521,68737,69001,69073,69457,69493,69697,69877,70117,70177,70297,70501,70621,70921,70981,71233,71341,71353,71593,71821,72073,72481,72613,72901,72937,73141,73417,73477,73561,73693,74077,74317,74377,74713,75013,75133,75181,75721,75793,75913,76333,76561,76597,76753,77137,77641,78157,78193,78277,78877,78901,79333,79357,79537,79657,79693,79801,79873,80077,80173,80221,80473,80701,80713,80917,81013,81181,81517,81637,81853,82021,82153,82261,82561,82981,83077,83221,83233,83437,83617,83701,83773,84121,84313,84673,84697,84793,84913,85297,85333,85453,85717,85933,86353,86413,87181,87253,87337,87421,87433,87517,87553,87973,88117,88177,88237,88261,88513,88741,88897,88993,89293,89833,89917,90121,91081,91381,91393,91513,91957,92041,92557,92761,92821,92893,92941,93097,93133,93493,93637,93913,94033,94117,94273,94321,94441,94573,94777,94837,94993,95257,95317,95401,95581,95617,95713,95737,96097,96157,96181,96493,96517,96973,97081,97177,97501,97561,97777,97813,98017,98737,98953,99277,99577,99661,99877,]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    ans=0
    for n in prime:
        if n>=l:
            if n<=r:
                ans+=1
            else:
                break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
prime = []
is_prime = []
is_prime.append(False)
is_prime.append(False)

def sieve(r):
    start = len(is_prime)
    if start >= r:
        return 

    for i in range(start, r + 1):
        is_prime.append(True)

    for i in prime:
        j = 2 * i
        while j <= r:
            if j < start:
                j = j + i
                continue

            is_prime[j] = False
            j = j + i

    for i in range(start, r + 1):
        if is_prime[i]:
            prime.append(i)

            j = 2 * i
            while j <= r:
                is_prime[j] = False
                j = j + i

def main():
    answers = []
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        sieve(r)
        like_numbers = [n for n in prime if n % 2 == 1 and l <= n <= r and is_prime[(n + 1) // 2]]
        answers.append(len(like_numbers))
    
    for answer in answers:
        print(answer)

main()

Submission status: Time Limit Exceeded

Solution code:
import math
def using_sqrt(limit):
    n = 0
    primes = set()
    for k in range(2, limit+1):
        factor = 0
        
        # 2以外の偶数は素数ではないので無視する
        if k % 2 == 0 and k != 2:
            continue
        
        # 繰り返しの上限を対象の平方根にする
        for divisor in range(2, math.floor(math.sqrt(k))+1):
            if k % divisor == 0:
                factor += 1
                
        if factor == 0:
            primes.add(k)
            
    return primes

primes = using_sqrt(10**5)

q = int(input())
for i in range(q):
    l, r = map(int,input().split())
    count = 0
    for j in range(l, r+1, 2):
        count += (j in primes and (j+1)/2 in primes )
    print(count)

Submission status: Time Limit Exceeded

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 t < len(lis) and lis[t] <= r:
        tmp += 1
        t += 1
    print(tmp)

Submission status: Time Limit Exceeded

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[p] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime

lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(10**5+1):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    t = lis[l:r+1].count(0)
    print(r-l+1-t)

Submission status: Time Limit Exceeded

Solution code:
def get_prime_number_list(N):
    primes = [2]
    limit = int(N**0.5)
    data = [i+1 for i in range(2, N, 2)]
    while 1:
        p = data[0]
        if limit <= p:
            return primes + data
        primes.append(p)
        data = [e for e in data if e%p != 0]

def main():
    Q=int(input())
    primes = get_prime_number_list(10**5)
    prime_lst = [0] * (10**5+10)
    for prime in primes:
        prime_lst[prime] = 1

    ans = [0]*(10**5+10)

    for i in range(3, 10**5+10, 2):
        if prime_lst[i] and prime_lst[(i+1)//2]:
            ans[i] += 1

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

main()

Submission status: Time Limit Exceeded

Solution code:
def check_similar_num_2017(N, prime_lst):
    return (N in prime_lst) and ((N+1)//2 in prime_lst)

def get_prime_number_list(N):
    prime_lst = [2]
    limit = int(N**0.5)
    data = [i+1 for i in range(2, N, 2)]
    while 1:
        p = data[0]
        if limit <= p:
            return prime_lst + data
        prime_lst.append(p)
        data = [e for e in data if e%p != 0]

def main():
    Q=int(input())
    prime_lst = get_prime_number_list(10**5)
    for _ in range(Q):
        cnt = 0
        l,r=map(int,input().split())
        for i in range(l, r+1, 2):
            cnt += check_similar_num_2017(i, prime_lst)
        print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

maximum = 100000
primes = sieve(maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if v and i >= l and i > 1 and i <= r and i % 2 == 1 and primes[(i + 1) // 2]:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

def segment_sieve(a, b):
    is_prime = [True] * (b - a)
    sqrt_b = math.ceil(math.sqrt(b))
    is_prime_small = [True] * (sqrt_b)

    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False
                j += i

            j = max(2, round((a + i - 1) // i)) * i
            while j < b:
                is_prime[j - a] = False
                j += i

        i+=1
        
    return is_prime

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

minimum = (min(l for l, r in LR) + 1) // 2
maximum = max(r for l, r in LR)
minimum = 0
primes = sieve(maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if i + minimum >= l and i + minimum > 1 and i + minimum <= r and (i + minimum) % 2 == 1 and v and primes[(i + minimum + 1) // 2 - minimum]:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

def segment_sieve(a, b):
    is_prime = [True] * (b - a)
    sqrt_b = math.ceil(math.sqrt(b))
    is_prime_small = [True] * (sqrt_b)

    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False
                j += i

            j = max(2, round((a + i - 1) // i)) * i
            while j < b:
                is_prime[j - a] = False
                j += i

        i+=1
        
    return is_prime
                

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

minimum = (min(l for l, r in LR) + 1) // 2
maximum = max(r for l, r in LR)
primes = segment_sieve(minimum, maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if i + minimum >= l and i + minimum > 1 and i + minimum <= r and (i + minimum) % 2 == 1 and v and primes[(i + minimum + 1) // 2 - minimum]:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

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+100,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)

def judge(a):
	return ((a in prime_arr)) and (((a+1)/2 in prime_arr))

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
	#print(x+1,y-1)
	#print(prime_arr[x+1],prime_arr[y-1])
	return sum(judge_arr[x+1:y])

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


for x in range(Q):
	print(sumz(data[x][0],data[x][1]+1))

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

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+100,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)

def judge(a):
	#return ((a in prime_arr) or a==2017) and (((a+1)/2 in prime_arr) or (a+1)/2==2017)
	return ((a in prime_arr)) and (((a+1)/2 in prime_arr))

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
	#print(x+1,y-1)
	#print(prime_arr[x+1],prime_arr[y-1])
	return sum(judge_arr[x+1:y])

judge_arr = [0]*len(prime_arr)
for n in range(len(prime_arr)):
	if judge(prime_arr[n]):
		judge_arr[n] = 1


for x in range(Q):
	num = 0
	#print(data[x][0],data[x][1]+1)
	print(sumz(data[x][0],data[x][1]+1))

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

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:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)

def judge(a):
	return ((a in prime_arr) or a==2017) and (((a+1)/2 in prime_arr) or (a+1)/2==2017)

for x in range(Q):
	num = 0
	for y in range(data[x][0],data[x][1]+1,2):
		#print(y)
		if judge(y):
			num+=1
	print(num)

Submission status: Time Limit Exceeded

Solution code:
def IsPrime(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for i in range(3, int(n ** 0.5 + 1), 2):
        if n % i == 0:
            return False
    return True


n = int(input())
q = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    l, r = q[i]
    cnt = 0
    for j in range(l, r + 1, 2):
        if IsPrime(j) and IsPrime((j + 1) // 2):
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

A = [2, 3]


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

for i in range(3, 100001):
    if is_prime(i):
        A.append(i)

# print(A)
B = [0] * 100001

for j in A:
    if (j + 1)//2 in A:
        B[j] = 1
for i in range(q):
    l, r = map(int, input().split())
    print(sum(B[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
def check(i):
    num=int(i**0.5)
    if i==1:return 0
    if i==2:return 1
    for j in range(2,num+1):
        if i%j==0:break

    else:return 1
    return 0
q=int(input())
lr=[list(map(int,input().split())) for i in range(q)]

L=[0]*(10**5)#1~100000
for i in range(1,10**5):
    L[i]=check(i+1)

for l,r in lr:
    cnt=0
    for i in range(l,r+1,2):
        if L[i-1]==0:continue
        if L[(i+1)//2-1]==0:continue
        cnt+=1

    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def check(i):
    num=int(i**0.5)
    if i==1:return 0
    if i==2:return 1
    for j in range(2,num+1):
        if i%j==0:break

    else:return 1
    return 0
q=int(input())
lr=[list(map(int,input().split())) for i in range(q)]

for l,r in lr:
    cnt=0
    for i in range(l,r+1,2):
        if check(i):
            next_num=int((i+1)//2)
            cnt+=check(next_num)
    print(cnt)

Submission status: Time Limit Exceeded

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

for l,r in lr:
    cnt=0
    for i in range(l,r+1,2):
        num=int(i**0.5)
        like_num=(i+1)//2
        if like_num==1:continue
        num2=int(like_num**0.5)
        for j in range(3,num+1,2):
            if i%j==0:break
        else:
            for j in range(2,num2+1):
                if like_num!=2 and like_num%j==0:break
            else:
                cnt+=1
                #print(i,cnt)
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [0]*N
B = [0]*N
for i in range(N):
  A[i],B[i] = map(int, input().split())
  
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

P = [0]*10**5
for i in range(1,10**5,2):
  P[i] = is_prime(i)
P[2]=True
ans = []   
for i in range(N):
  cnt = 0
  for j in range(A[i],B[i]+1,2):
    if P[j]==True and P[(j+1)//2]==True:
      cnt += 1
  ans.append(cnt)

print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
#自然数m以下の素数を返す
def prime_numbers(m):
    primes = set()
    n = 2
    while n <= m:
        if all(n % i != 0 for i in primes):
            primes.add(n)
        n += 1
    return primes

q = int(input())
l = []
r = []
for i in range(q):
    L,R = map(int,input().split())
    l.append(L)
    r.append(R)

p = prime_numbers(max(r))
cnt = [0 for i in range(max(r)+1)]
for i in p:
    if (i + 1) // 2 in p:
        cnt[i]+=1

for i in range(1,len(cnt)):
    cnt[i]+=cnt[i - 1]

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

Submission status: Time Limit Exceeded

Solution code:
def erat(n):
    l = [1 for _ in range(n)]
    i = 0
    while (i < n):
        if i == 0:
            l[i] = 0
        elif l[i] == 1:
            for j in range(i + 2, n + 1):
                if not j % (i + 1):
                    l[j - 1] = 0
            # l = list(map(lambda x: 1 if x % (i + 1) else 0, l))
        i += 1

    return l


n_max = 10**5

is_prime = erat(n_max)
is_2017 = [0 for _ in range(n_max)]
for i in range(2, n_max + 1):
    if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]:
        is_2017[i - 1] = 1

s = [0]
for i in range(n_max):
    s.append(s[i] + is_2017[i])


print('plz input.')
q = int(input())
ans = []
for _ in range(q):
    li, ri = map(int, input().split())
    ans.append(s[ri] - s[li - 1])

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
MAX = 100000

def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)
        inP_list[prime] = True

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)
        inP_list[a]=True

    return P

inP_list = [False]*MAX
p_list=eratosthenes(MAX)

ans_sum_list = [0] * MAX

for i in range(3,MAX, 2):
    if inP_list[i] and inP_list[(i+1)//2]:
        ans_sum_list[i] += 1
    ans_sum_list[i] += ans_sum_list[i-2]

q = int(input())
ans = [0]*q
for i in range(q):
    l, r = map(int, input().split())
    ans[i] = ans_sum_list[r] - ans_sum_list[max(1,l-2)]

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import math

def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)

    return P

p_list=eratosthenes(10000)

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

q = int(input())
ans = [0]*q
for i in range(q):
    l, r = map(int, input().split())
    tmp = 0
    for j in range (l,r+1,2):
        if j in p_list and (j+1)//2 in p_list: tmp+=1
    ans[i] = tmp

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
Q = int(input())
l = []
r = []
for i in range(Q) :
    p, q = map(int,input().split())
    l.append(p)
    r.append(q)

def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    while True:
      if search_list[0]**2 > number:
        prime_list.extend(search_list)
        break
      else:
        head_num = search_list[0]
        prime_list.append(head_num)
        search_list.pop(0)
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

primes = get_primenumber(10**5+1)

for i in range(Q) :
    ans = 0
    for j in range(l[i],r[i]+1) :
        if j%2 == 0 :
            continue
        if j in primes and (j+1)//2 in primes :
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return set(prime + data)
        prime.append(p)
        data = [e for e in data if e % p != 0]


Q = int(input())
lr = [None] * Q
for i in range(Q):
    lr[i] = tuple(map(int, input().split()))
eratosthenes = get_sieve_of_eratosthenes(10**5)

for i in range(Q):
    ans = 0
    for N in range(lr[i][0], lr[i][1] + 1, 2):
        M = (N + 1) // 2
        if N in eratosthenes and M in eratosthenes:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt


def is_Prime(N):
    if N == 1:
        return False
    rootN = int(sqrt(N))
    for i in range(2, rootN + 1):
        if N % i == 0:
            return False
    else:
        return True


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

for i in range(Q):
    ans = 0
    for N in range(lr[i][0], lr[i][1] + 1, 2):
        M = (N + 1) // 2
        if is_Prime(N) and is_Prime(M):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
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
ko0=[]
ko=[]
for i in range(1,10**5,2):
    if is_prime((i+1)//2)==True:
        ko0.append(i)  
for i in ko0:
    if is_prime(i)==True:
        ko.append(i)
for i in range(q):
    l,r=map(int,input().split())   
    ans0=1
    ans1=0
    for i in range(len(ko)):
        if l<=ko[i]:
            ans0=i
            break
    for i in range(len(ko)):
        if r<ko[i]:
            ans1=i-1
            break
    print(ans1-ans0+1)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
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
ko=[]
for i in range(1,10**5,2):
    if is_prime((i+1)//2)==True:
        if is_prime(i)==True:
            ko.append(i)      
for i in range(q):
    l,r=map(int,input().split())   
    ans0=1
    ans1=0
    for i in range(len(ko)):
        if l<=ko[i]:
            ans0=i
            break
    for i in range(len(ko)):
        if r<ko[i]:
            ans1=i-1
            break
    print(ans1-ans0+1)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
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
ko=[]
for i in range(1,10**5,2):
    if is_prime((i+1)//2)==True:
        if is_prime(i)==True:
            ko.append(i)
        
for i in range(q):
    l,r=map(int,input().split())
    s=l
    count=0
    while s<=r:
        if s in ko:
            count+=1
        s+=2
    print(count)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
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
for i in range(q):
    l,r=map(int,input().split())
    s=l
    count=0
    while s<=r:
        if is_prime((s+1)//2)==True:
            if is_prime(s)==True:
                count+=1
        s+=2
    print(count)

Submission status: Time Limit Exceeded

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 [i for i in range(n + 1) if is_prime[i]]

tmp = 0
MAX = 100000
prime = primes(MAX)
a = [0 for _ in range(MAX+1)]
for i in range(MAX+1):
    if i%2 == 0:
        continue
    elif i in prime and int((i+1)/2) in prime:
        a[i] = 1
#累積和
s = [0 for _ in range(MAX+2)]
for i in range(MAX+1):
    s[i+1] = s[i] + a[i]


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

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import accumulate

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())
for _ in range(q):
    l, r = map(int, input().split())
    A = [i for i in range(l, r+1, 2)]
    B = [(a+1)//2 for a in A]
    A_B = [0] +[1 for i in range(len(A)) if is_prime(A[i]) and is_prime(B[i])]
    print(max(accumulate(A_B)))

Submission status: Time Limit Exceeded

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())
for _ in range(q):
    l, r = map(int, input().split())
    A = [i for i in range(l, r+1, 2)]
    B = [(a+1)//2 for a in A]
    cnt = 0
    for i in range(len(A)):
      if is_prime(A[i]) and is_prime(B[i]):
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
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())
for _ in range(q):
    l, r = map(int, input().split())
    A = [i for i in range(l, r+1, 2)]
    B = [(a+1)//2 for a in A]
    cnt = 0
    for i in range(len(A)):
      if is_prime(A[i]) and is_prime(B[i]):
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    def prime_decomp(n):
        i = 2
        res = []
        while i ** 2 <= n:
            while n % i==0:
                n //= i
                res.append(i)
            i += 1
        if n > 1:
            res.append(n)
        return res
    
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        res = 0
        for i in range(l, r+1, 2):
            if len(prime_decomp(i))==1:
                if len(prime_decomp((i+1)//2))==1:
                    res += 1
        print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = [False,False ] + [True for _ in range(10**5-1)]

def check_prime(x):
    for i in range(x*2,10**5+1,x):
        n[i] = False

check_prime(2)
for i in range(3,10**5+1,2):
    check_prime(i)

for _ in range(int(input())):
    l,r = map(int,input().split())
    ans = 0
    for i in range(l,r+1):
        if i % 2 == 1 and n[i] and n[(i+1)//2]:
           ans += 1
    print (ans)