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
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N=10**5
p=[1]*(N+1)
p[0]=p[1]=0
q=[0]*(N+1)
for i in range(2,N+1):
    if p[i]==1:
        tmp=2*i
        while tmp<=N:
            p[tmp]=0
            tmp+=i
    if i%2!=0 and p[i]==1 and p[(i+1)//2]==1:
        q[i]=q[i-1]+1
    else:
        q[i]=q[i-1]
Q=intput()
for _ in range(Q):
    l,r=mint()
    print(q[r]-q[l-1])

Solution (Python):

import sys
from collections import deque
from collections import defaultdict
from itertools import accumulate

import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)




def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


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 = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


max_ = pow(10, 5) + 2
primes = get_sieve_of_eratosthenes(max_)
num_lile2017 = [0]*max_
primes2 = []
for prime in primes:
    primes2.append(2*prime-1)
like2017 = sorted(list(set(primes2) & set(primes)))
for i in range(3, max_, 2):
    if (i in like2017):
        num_lile2017[i] = 1
num_lile2017 = list(accumulate(num_lile2017))


Q = z()
for i in range(Q):
    l, r = zz()
    print(num_lile2017[r] - num_lile2017[l-1])

Solution (Python):
import math
from itertools import accumulate

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

MAX=10**5
lim=int(math.sqrt(MAX))
primes=[2]
table=[i+1 for i in range(2,MAX,2)]
while lim>table[0]:
  primes.append(table[0])
  table=[j for j in table if j%table[0]!=0]
primes=set(primes+table)

similars=[0]*MAX
for i in range(2,MAX):
  if i in primes and (i+1)//2 in primes:
    similars[i]=1
similars=list(accumulate(similars))

for i in lr:
  l,r=i
  print(similars[r]-similars[l-1])

Solution (Python):
import sys



def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def gen_prime_table(last: int, first=2) -> list:
    if last < 1:
        return [False]
    elif last < 2:
        return [False, False]
    primes = []
    table = [True] * (last + 1)
    table[0] = False
    table[1] = False

    for i in range(first, last + 1):
        if table[i]:
            primes.append(i)
            for j in range(i * 2, last + 1, i):
                table[j] = False
    return table


def main():
    q = input_int()
    prime_table = gen_prime_table(10**5 + 1)
    prime_cusum = [0] * (10**5 + 1)
    for i in range(1, 10**5):
        if prime_table[i] and prime_table[(i + 1) // 2]:
            prime_cusum[i] = prime_cusum[i - 1] + 1
        else:
            prime_cusum[i] = prime_cusum[i - 1]

    for _ in range(q):
        l, r = input_int_list()
        print(prime_cusum[r] - prime_cusum[l - 1])

    return


if __name__ == "__main__":
    main()

Solution (Python):
def is_prime(N):
    if N == 1: return False
    if N == 2: return True
    
    d = 2 
    while d*d <= N:
        if N % d == 0: return False
        d += 1
    return True

Q = int(input())

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

for q in range(Q):
    l, r = map(int,input().split())
    print(S[r] - S[max(0,l-2)])

Solution (Python):
Q = int(input())

is_prime = [True] * 100010
for i in range(100010):
    if i <= 1:
        is_prime[i] = False
        continue

    if is_prime[i]:
        for j in range(2*i,100010,i):
            is_prime[j] = False

is_2017like_prime = [False] * 100010
for i in range(1,100010,2):
    if is_prime[i] & is_prime[(i+1)//2]:
        is_2017like_prime[i] = True

cumsum = [0]
for a in is_2017like_prime[1:]:
    cumsum.append(cumsum[-1] + a)

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

Solution (Python):
Q = int(input())

N=10**5
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]]

F = primes(N)
F_2007=[]

a = [0]*(N+1)

for f in F:
    a[f] = 1

for f in F:
    if a[(f+1)//2] == 1:
        F_2007.append(f)
        
a = [0]*(N+1)
for f in F_2007:
    a[f] = 1
    
a_sum = [0]
for a_ in a:
    a_sum.append(a_sum[-1]+a_)
a_sum=a_sum[1:]

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

Solution (Python):
Q = int(input())

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

y = [0]*lim
for i in range(3, lim, 2):
    y[i] = y[i-2]
    if p[i] and p[(i+1)//2]:
        y[i] += 1
    y[i-1] = y[i-2]

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

Solution (Python):
q=int(input())


prime=[0 for i in range(10**5+5)]
for i in range(2,10**5+5):
  j=1
  if not prime[i]:
    while j*i<=10**5+4:
      prime[j*i]=i
      j+=1

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

like2017sum=[0 for i in range(10**5+5)]
for i in range(10**5+4):
  like2017sum[i+1]=like2017sum[i]+like2017[i+1]


for i in range(q):
  l,r=map(int,input().split())
  if like2017[l]==1:
    alpha=1
  else:
    alpha=0
  print(like2017sum[r]-like2017sum[l]+alpha)

Solution (Python):
q = int(input())
n = 10**5
nums = [False]*2+[True]*(n-2)
ans = [0]*n
for i in range(2, n):
    if nums[i]:
        for j in range(i*2, n, i):
            nums[j] = False
pre = 0
for i in range(3, n, 2):
    if nums[i] and nums[(i+1)//2]:
        ans[i] += pre+1
        pre = ans[i]
    else:
        ans[i] = pre
for _ in range(q):
    l, r = map(int, input().split())
    print(ans[r]-ans[max(l-2, 1)])

Solution (Python):
MAX=101010
is_prime=[True]*MAX
is_prime[0]=False
is_prime[1]=False
for i in range(2,MAX):
  if is_prime[i]==False:
    continue
  for j in range(i*2,MAX,i):
    is_prime[j]=False

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

s=[0]
for x in a:
  s.append(s[-1]+x)

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

Solution (Python):
from math import sqrt
import bisect


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

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

    return True


def solve(query):
    ans = []
    al = []
    for i in range(3, 10**5+1, 2):
        if is_prime(i) and is_prime((i+1)//2):
            al.append(i)

    for q in query:
        if is_prime(q[0]) and is_prime((q[0]+1)//2):
            l_ind = bisect.bisect_right(al, q[0]) - 1
        else:
            l_ind = bisect.bisect_right(al, q[0])
        if is_prime(q[1]) and is_prime((q[1]+1)//2):
            r_ind = bisect.bisect_left(al, q[1])
        else:
            r_ind = bisect.bisect_left(al, q[1]) - 1
        ans.append(r_ind-l_ind+1)

    return ans


if __name__ == "__main__":
    Q = int(input())
    query = [list(map(int, input().split())) for _ in range(Q)]

    ans = solve(query)

    for a in ans:
        print(a)

Solution (Python):
import math

def main():
	prime = [2, 3, 5, 7]
	for n in range(11, 100001):
		for p in prime:
			if n % p == 0:
				break
			if p > math.sqrt(n):
				prime.append(n)
				break
	sim = []
	j = 0
	for i in range(1, len(prime)):
		p = prime[i]
		q = int((p + 1) / 2)
		while q > prime[j]:
			j += 1
		else:
			if q == prime[j]:
				sim.append(p)
	sim.append(12345678)

	sim_n = [0]
	k = 0
	for s in range(1, 100001):
		if s == sim[k]:
			sim_n.append(sim_n[-1] + 1)
			k += 1
		else:
			sim_n.append(sim_n[-1])

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

main()

Solution (Python):

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



isPrime = makePrimeChecker(100000)
Q = int(input())
L=[0]


for i in range(1, 100000):
	if i&1==1 and isPrime[i] and isPrime[(i+1)//2]:
		L.append(L[-1]+1)
	else:
		L.append(L[-1])

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

Solution (Python):

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





Q = int(input())
L = [0]
isPrime = makePrimeChecker(100000)
for i in range(1, 100000):
    if i&1==1 and isPrime[i] and isPrime[(i+1)//2]:
        L.append(L[-1] + 1)
    else:
        L.append(L[-1])
for i in range(Q):
    l, r = map(int, input().split())
    print(L[r] - L[l-1])

Solution (Python):
import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

MaxQ = 10**5+1
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

a = [0]*MaxQ
s = [0]*MaxQ
prime = isPrime_np(MaxQ)
pset = set(prime)
for p in prime:
    if (p+1)/2 in pset:
        a[p] = 1

ans = []
s = np.cumsum(a)
    
for l,r in lr:
    ans.append(s[r] - s[l-1])
print(*ans,sep="\n")

Solution (Python):
import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

MaxQ = 10**5+1
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

a = [0]*MaxQ
s = [0]*MaxQ
prime = isPrime_np(MaxQ)
pset = set(prime)
for p in prime:
    if (p+1)/2 in pset:
        a[p] = 1

ans = []
for i in range(MaxQ-1):
    s[i+1] = s[i] + a[i]
    
for l,r in lr:
    ans.append(s[r+1] - s[l])
print(*ans,sep="\n")

Solution (Python):
n_max = 10 ** 5 + 10
sieve = [0, 0] + [1]*n_max
m = 2
while m * m <= n_max:
    if sieve[m]:
        for n in range(2*m, n_max, m):
            sieve[n] = 0
    m += 1

ok = [0]*n_max
cums = [0]
for n in range(n_max):
    if sieve[n] and sieve[(n+1)//2]:
        ok[n] = 1
    cums.append(cums[-1]+ok[n])

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

Solution (Python):
def sieve(n):
    from math import sqrt
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = is_prime[1] = False
    for i in range(int(sqrt(n))+1):
        if is_prime[i]:
            for k in range(2, n//i+1):
                is_prime[i*k] = False
    return is_prime

def is_like2017(n):
    for i in range(n+1):
        if is_primeL[i]:
            
            if is_primeL[(i+1)//2]:
                is_likeL[i] = True

n = 100000
is_primeL = sieve(n)
is_likeL = [False for _ in range(n+1)]
is_like2017(n)

from itertools import accumulate

cumL = list(accumulate(is_likeL))
cumL[0] = 0

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

Solution (Python):
def prime_checker_range(n): 
    ls = [i for i in range(2,n)]
    p = 0
    while True:
        new_ls = [j for j in ls if (j % ls[p] != 0) or (j <= ls[p])]
        ls = new_ls
        if ls[p]**2 >= max(ls):
            return ls
        else:
            p += 1
    return ls
def prime_checker(i): 
    if i == 1:
        return False
    else:
        for j in range(2,(int(i**0.5))+1):
            if i % j == 0:
                return False
            else:
                continue
        return True
q = int(input())
ls = [i for i in prime_checker_range(10**5+1) if prime_checker((i+1)//2)]
di = [0]*(10**5+1)
c = 1
for p in range(len(ls)):
    if p != len(ls)-1:
        for m in range(ls[p],ls[p+1]):
            di[m] = c
    else:
        for m in range(ls[p],10**5+1):
            di[m] = c
    c += 1
for k in range(q):
    l,r = map(int,input().split())
    print(di[r]-di[l-1])