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:
Q = int(input())
lr = []
maxr = 0
for i in range(Q):
    l,r = map(int,input().split())
    maxr = max(maxr,r)
    lr.append([l,r])
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]]
prime = primes(maxr)
prime2 = [0 for i in range(maxr+1)]
for i in prime:
    if (i+1)/2 in prime:
        prime2[i] += 1
for i in range(maxr):
    prime2[i+1] += prime2[i]
for l,r in lr:
    print(prime2[r]-prime2[l-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left

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())
fn=[99999 for i in range(10**5+100)]
for i in range(Q):
    
    L, R=map(int, input().split())
    for x in range(L, R+1):
        if fn[x] != 99999:
            continue
        if is_prime(x) and is_prime(int((x+1)/2)):
            fn[x] = 1
        else:
            fn[x] = 0
    print(sum(fn[L:R+1]))

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())
L = [0]*Q
R = [0]*Q
for i in range(Q):
    L[i], R[i] = map(int, input().split())

# print(Q, L, R)

def gen_primes():
    max_lr = 10**5
    primes = [2]
    for i in range(3, max_lr, 2):
        is_prime = True
        limit = int(math.sqrt(i)) + 1
        for p in primes:
            if p > limit:
                break
            if i % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
    # print(len(primes))
    return primes

primes = gen_primes()

def is_2017_like(n):
    m = (n + 1) // 2
    return n in primes and m in primes

for i in range(Q):
    ans = 0
    for j in range(L[i], R[i] + 1, 2):
       if is_2017_like(j):
           ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = 10**5
e = [True]*(n+1)
e[0] = False
e[1] = False
for i in range(2, int(n**0.5)+1):
    if not e[i]:
        continue
    for j in range(i*2, n+1, i):
        e[j] = False

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())

    ans = 0
    for i in range(l, r+1, 2):
        if e[i] and e[(i+1)//2]:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    LR.append(list(map(int,input().split())))
    l,r=LR[-1]
    L=l if l>L else L
    R=r if r>R else R

M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=set()
a=2
count=0
for a in range(2,M):
    if a in numlst:
        numlst.remove(a)
        if a:
            sosuulst.add(a)
        numLst=list(numlst)
        for i in numLst:
            if i%a==0:
                numlst.remove(i)
        if (a+1)//2 in sosuulst:
            count+=1
    if a>=3:
        lst[a]=count
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Submission status: Time Limit Exceeded

Solution code:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=set()
a=2
count=0
for a in range(2,M):
    if a in numlst:
        numlst.remove(a)
        if a:
            sosuulst.add(a)
        numLst=list(numlst)
        for i in numLst:
            if i%a==0:
                numlst.remove(i)
        if (a+1)//2 in sosuulst:
            count+=1
    if a>=3:
        lst[a]=count
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Submission status: Time Limit Exceeded

Solution code:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=[]
a=2
while numlst:
    while not a in numlst:
        a+=1
    numlst.remove(a)
    if a:
        sosuulst.append(a)
    numLst=list(numlst)
    for i in numLst:
        if i%a==0:
            numlst.remove(i)

sosuulst=set(sosuulst)

count=0
for i in range(2,M):
    if i in sosuulst and (i+1)//2 in sosuulst:
        count+=1
    lst[i]=count

for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Submission status: Time Limit Exceeded

Solution code:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=[]
dellist=set()
a=2
while numlst:
    while not a in numlst:
        a+=1
    numlst.remove(a)
    if a:
        sosuulst.append(a)
    dellist.clear()
    for i in numlst:
        if i%a==0:
            dellist.add(i)
    for i in dellist:
        numlst.remove(i)

sosuulst=set(sosuulst)

count=0
for i in range(2,M):
    if i in sosuulst and (i+1)//2 in sosuulst:
        count+=1
    lst[i]=count

for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Submission status: Time Limit Exceeded

Solution code:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=[]
dellist=set()
while numlst:
    a=min(numlst)
    numlst.remove(a)
    if a:
        sosuulst.append(a)
    dellist.clear()
    for i in numlst:
        if i%a==0:
            dellist.add(i)
    for i in dellist:
        numlst.remove(i)
sosuulst=set(sosuulst)

count=0
for i in range(2,M):
    if i in sosuulst and (i+1)//2 in sosuulst:
        count+=1
    lst[i]=count

for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Submission status: Time Limit Exceeded

Solution code:

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

M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

for i in range(n):
	count = 0
	num = input().split(" ")
	for j in range(int(num[0]), int(num[1]) + 1):
		if f(j):
			if f(int((j + 1) / 2)):
				count += 1
	print(count)

Submission status: Time Limit Exceeded

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

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

def lnum(n):  # Like number
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False

ans = [0]*q
for j in range(q):
    for k in range(a[j][0], a[j][1]+1, 1):
        if lnum(k):
            ans[j] += 1
        else:
            continue
for x in ans:
    print(x, end=" ")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import math
import bisect
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

def isOK(index,key):
    if l[index] <= key:
        return True
    else:
        return False

def binary_search(key):
    left=len(l)-1
    right=-1
    
    while abs(right - left) >1:
        mid=(right+left)//2
        
        if isOK:
            right=mid
        else:
            left=mid
    return right

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

primes=callIsPrime(10**5)
l=[]

for i in range(len(primes)):
    if (primes[i]+1)//2 in primes:
        l.append(primes[i])
        
Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    L=bisect.bisect_left(l,L)
    R=bisect.bisect_right(l,R)
    
    print(R-L)

Submission status: Time Limit Exceeded

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[1])

    for l,r in Queries:
        temp=[i for i in p_list if l<=i<=r and is_prime((i+1)//2)]
        if l!=1:
            print(len(temp))
        if l==1:
            print(len(temp)-1)

Submission status: Time Limit Exceeded

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[1])

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

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)]

    for l,r in Queries:
        count=0
        p_list=make(r)
        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: Time Limit Exceeded

Solution code:
def get_primes(l, r):
    data = [False]* 2 + [True for _ in range(2, r+1)]
    for i in range(2, r+1):
        for j in range(i*2, r+1, i):
            data[j] = False
    primes = [i for i in range(l, r+1) if data[i]]
    return primes

def is_prime(num):
    if num < 2:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False

    for i in range(3, int(num**0.5)+1, 2):
        if num % i == 0:
            return False
    else:
        return True

if __name__ == "__main__":
    Q = int(input())
    l_r = [list(map(int, input().split())) for _ in range(Q)]
    for i in range(Q):
        count = 0
        for j in get_primes(l_r[i][0], l_r[i][1]):
            if is_prime((j + 1) / 2):
                count += 1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
prime = [3, 5]
for i in range(13, 102010, 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: Time Limit Exceeded

Solution code:
# coding: utf-8
def check(x):
    flag = True
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            flag = False
            break
    return flag
Q = int(input())
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    if l == 1:
        l += 2
    for v in range(l, r+1, 2):
        t1 = check(v)
        t2 = check((v+1)//2)
        if t1 and t2:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
    '''
    素数判定する
    '''
    if n == 1:
        return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True


Q = int(input())
prime_list = [None] * 100001
for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    for i in range(l, r+1, 2):
        i2 = (i + 1) // 2
        if prime_list[i] == None:
            prime_list[i] = is_prime(i)
        if prime_list[i2] == None:
            prime_list[i2] = is_prime(i2)
        ans += 1 if prime_list[i] and prime_list[i2] else 0
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# [l,r]での素数リスト
def primes(l,r):
    is_prime = [True] * (r + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(r**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, r + 1, i):
            is_prime[j] = False
    return len([i for i in range(l,r + 1) if is_prime[i] and i % 2 == 1 and is_prime[(i+1)//2]])

import sys
input = sys.stdin.readline

Q = int(input())
lr = [[int(i) for i in input().split()] for _ in range(Q)]

for i in range(Q):
    print(primes(lr[i][0],lr[i][1]))

Submission status: Time Limit Exceeded

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

memo=[-1]*(10**5+1)
memo[1]=0
def is_prime1(n):
    if memo[n]!=-1:
        return(memo[n]==1)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            memo[n]=0
            return False
    memo[n]=1
    return True

p=[True]*(10**5+1)
def is_prime2(n):
    return(p[n])

def sleve():
    p[0]=False
    p[1]=False
    primes=[]
    for i in range(2,10**5+1):
        if p[i]:
            primes.append(i)
            for j in range(2*i, 10**5+1, i):
                p[j]=False

sleve()
is_prime=is_prime2
for l,r in queries:
    ans=0
    for n in range(l,r+1):
        if n&1:
            if is_prime(n) and is_prime((n+1)//2):
                ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

memo=[-1]*(10**5+1)
memo[1]=0
def is_prime(n):
    if memo[n]!=-1:
        return(memo[n]==1)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            memo[n]=0
            return False
    memo[n]=1
    return True

for l,r in queries:
    ans=0
    for n in range(l,r+1):
        if n&1:
            if is_prime(n) and is_prime((n+1)//2):
                ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect, bisect_left
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def get_sieve_of_eratosthenes(n):
	prime = [2]
	limit = int(n**0.5)
	data = [i + 1 for i in range(2, n, 2)]
	append = prime.append
	while True:
		p = data[0]
		if p > limit:
			return prime + data
		append(p)
		data = [e for e in data if e % p != 0]

def main():
	Q = INT()
	A = [[] for _ in range(Q)]
	
	qmax = 0
	for i in range(Q):
		l, r = MAP()
		qmax = max(qmax, r)
		A[i] = [l, r]
	
	primes = get_sieve_of_eratosthenes(qmax)
	primes = [p for p in primes if primes.count((p+1)//2)]
	# print(primes)

	for a in A:
		l, r = a
		print(bisect(primes, r)-bisect_left(primes, l))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect, bisect_left
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def get_sieve_of_eratosthenes(n):
	prime = [2]
	limit = int(n**0.5)
	data = [i + 1 for i in range(2, n, 2)]
	append = prime.append
	while True:
		p = data[0]
		if p > limit:
			return prime + data
		append(p)
		data = [e for e in data if e % p != 0]

def main():
	import time
	primes = get_sieve_of_eratosthenes(10**5)
	primes = [p for p in primes if primes.count((p+1)//2)]
	# print(primes)
	Q = INT()
	for _ in range(Q):
		l, r = MAP()
		print(bisect(primes, r)-bisect_left(primes, l))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
C=[0]*(10**5+2)
C[0]=1
C[1]=1
S=[0]*(10**5+2)
t=1
while(t<=(10**5)):
    t+=1
    if(C[t]==1):
        continue
    k=1
    while(True):
        k+=1
        if(t*k>(10**5)):
            break 
        C[t*k]=1

for i in range(1,(10**5),2):
    if(C[i]==0):
        if(C[(i+1)//2]==0):
            S[i]=1

N=int(input())
for i in range(N):
    l,r=map(int,input().split())
    c=0
    T=S[l:r+1]
    print(sum(T))

Submission status: Time Limit Exceeded

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

t=1
while(t<=(10**5)):
    t+=1
    if(C[t][0]==1):
        continue
    k=1
    while(True):
        k+=1
        if(t*k>(10**5)):
            break 
        C[t*k][0]=1
        
for i in range(1,(10**5),2):
    if(C[i][0]==0):
        if(C[(i+1)//2][0]==0):
            C[i][1]=1

N=int(input())
for i in range(N):
    l,r=map(int,input().split())
    c=0
    for j in range(l,r+1):
        if(C[j][1]==1):
            c+=1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import math

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]]


q = int(input())
l_r = []
for _ in range(q):
    l, r = map(int, input().split())
    l_r.append((l,r))

can = primes(10**5)
like_2017 = []

for m in can:
    limit = (max(can)//2)
    if m > limit :
        break
    if 2*m-1 in can:
        like_2017.append(2*m-1)

count = 0
can_count = []
for i in range(10**5):
    if i in like_2017:
        count += 1
    else:
        pass
    can_count.append(count)

for pair in l_r:
    l = pair[0]
    r = pair[1]
    ans = can_count[r] - can_count[l-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def Sieve_of_Eratosthenes(n):
    if n < 2:
        raise ValueError('n is more than 2.')
    prime = []
    limit = math.sqrt(n)
    can = [i for i in range(2, n+1)]
    while True:
        p = can[0]
        if limit <= p:
            return prime + can
        prime.append(p)
        can = [x for x in can if x%p != 0]

q = int(input())
l_r = []
for _ in range(q):
    l, r = map(int, input().split())
    l_r.append((l,r))

can = Sieve_of_Eratosthenes(10**5)
like_2017 = []

for m in can:
    limit = (max(can)//2)
    if m > limit :
        break
    if 2*m-1 in can:
        like_2017.append(2*m-1)

count = 0
can_count = []
for i in range(10**5):
    if i in like_2017:
        count += 1
    else:
        pass
    can_count.append(count)

for pair in l_r:
    l = pair[0]
    r = pair[1]
    ans = can_count[r] - can_count[l-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
S=[]
for i in range(1,10**5):
  if is_prime(i) and is_prime((i+1)//2):
    S+=[i]

N=int(input())
for i in range(N):
  l,r = map(int,input().split())
  count=0
  for j in range(l,r+1):
    if j in S:
      count +=1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    q=int(input())
    aa=0
    bb=0
    a=[]
    b=[]
    ac=[]
    bc=[]
    for _ in range(q):
        aa,bb=map(int,input().split())
        a.append(aa)
        b.append(bb)
        # ac.append(aa)
        # bc.append(bb)

    # sorted(a)
    # sorted(b)
    bm=max(b)
    ans=[0]*100001
    flg=[0]*100001
    flg[0]=1
    flg[1]=1
    ans[2]=1
    ii=int((bm+1)**0.5)
    for i in range(2,100001):

        if flg[i]==0:
            flg[i]=1
            ans[i]=1
            for j in range(i,int(100001**0.5),i):
                flg[j]=1
    for i in range(0,q):
        cnt=0
        for j in range(a[i],b[i]+1):
            if ans[j]==1 and ans[(j+1)//2]==1:
                cnt+=1
        print(cnt)
    # print(ans[:8])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

Q = int(input())
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())

A = list(range(2,max(r)+1))
sqrt_n = (max(r)+1)**(1/2)
idx = 0

while True:
    p = A[idx]
    if p > sqrt_n:
        break
    q = 2*p
    while q <= max(r):
        if q in A:
            A.remove(q)
        q += p
    idx += 1

ans = [0] * (max(r)+1)
for a in A:
    if (a+1)//2 in A:
        ans[a] += 1
ans = list(accumulate(ans))

for i,j in zip(l,r):
    print(ans[j]-ans[i-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

Q = int(input())
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())

A = list(range(2,max(r)+1))
sqrt_n = (max(r)+1)**(1/2)
idx = 0

while True:
    p = A[idx]
    if p > sqrt_n:
        break
    check_numbers = A[idx+1:]
    for check_number in check_numbers:
        if check_number % p == 0:
            A.remove(check_number)
    idx += 1

ans = [0] * (max(r)+1)
for a in A:
    if (a+1)//2 in A:
        ans[a] += 1
ans = list(accumulate(ans))

for i,j in zip(l,r):
    print(ans[j]-ans[i-1])