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

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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))

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):

from itertools import accumulate

def sieve(n: int) -> 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)
    

    
_2017_like = [1 if i in primelist and (i + 1) // 2 in primelist else 0 for i in range(10**5+1)]
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)))

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
from math import sqrt
def is_prime(n) :
    if (n <= 1) :
        return False
    if (n <= 3) :
        return True
    
    if (n % 2 == 0 or n % 3 == 0) :
        return False
    i = 5
    while(i * i <= n) :
        
        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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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
            


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


cumsum = like_2017.cumsum()

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

Solution (Python):
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()

Solution (Python):

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)

Solution (Python):
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()))


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




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

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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_list=[2]
  for num in range(3,N+1,2):
    if all(num%prime != 0 for prime in prime_list):
      prime_list.append(num)
  return prime_list

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

Solution (Python):

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
 



 




 


 





 


 



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)
        
    
    for i in range(Q):
        l,r = inputMap()
        
        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
     




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

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):


import numpy as np
def list_primes(N):
    is_prime = np.ones(N+1, dtype=np.bool)
    
    is_prime[0] = False
    is_prime[1] = False
    for i in range(N+1):
        if is_prime[i]:
            is_prime[2*i::i] = False
            
    
    return is_prime
    
    
N = 10**5
is_prime = list_primes(N)



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): 
    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
        
        if A[ma] == a:return ma+1
        else: return ma

def nibu_left(a,A): 
    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
        
        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)

Solution (Python):
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 

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