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 math 

def prime(n):
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0
    return 1


MAX =100000
is_prime = [1]*(MAX+1)
is_prime[0] = 0 
is_prime[1] = 0
for i in range(2,MAX+1):
    if prime(i) == 1:
        j = i*2
        while j <= MAX:
            is_prime[j] = 0
            j += i


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


s = [0] * (MAX+1)
for i in range(0,MAX):
    s[i+1] = s[i] + a[i]


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

    print(s[r]-s[l])

Solution (Python):
from itertools import accumulate
Q = int(input())
ans = []
def eratosthenes(N):
    searchList = [i for i in range(2,N)]
    primeNum = []


    mx = int(N**0.5+1)
    while searchList[0] <= mx:
        primeNum.append(searchList[0])
        tmp = searchList[0]
        searchList = [i for i in searchList if i%tmp != 0]
    primeNum.extend(searchList)
    return primeNum

ok = [0]*(10**5+1)
primeNum = eratosthenes(10**5+1)
primeNumLst = [False] * (10**5+1)

for p in primeNum:
    primeNumLst[p] = True

for p in primeNum:
    if primeNumLst[(p+1)//2]:
        ok[p] = 1
    
ok = list(accumulate(ok))

for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(ok[r] - ok[l-1])
    
print("\n".join(map(str,ans)))

Solution (Python):
import math
def isprime(n):
    if n==1:return(False)
    if n==2:return(True)
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:return(False)
    return(True)
s=set([i for i in range(1,10**5,4) if isprime(i) and isprime((i+1)//2)])
s.add(3)
l=[i in s for i in range(10**5)]
ls=[]
tmp=0
for i in l:
    tmp+=i
    ls.append(tmp)
n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    print(ls[r]-ls[l-1])

Solution (Python):
def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return p


p, c = primes(10 ** 5), [0]
for i in range(1, 10 ** 5 + 1):
    c.append(c[-1] + 1 if p[i] and p[(i + 1) // 2] else c[-1])

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

Solution (Python):
def primes(N):
    '''Sieve of Eratosthenes'''
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return p


p, c = primes(10 ** 5), [0]
for i in range(1, 10 ** 5 + 1):
    c.append(c[-1] + 1 if p[i] and p[(i + 1) // 2] else c[-1])

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

Solution (Python):
import math
from bisect import bisect_left, bisect_right

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

is_prime = [False for _ in range(100001)]
is_prime[3] = True
primes = [3]
for n in range(5, 100001, 2):
    prime = True
    i = 2
    while i < int(math.sqrt(n)) + 1:
        if n % i == 0:
            prime = False
            break
        i += 1
    if prime:
        primes.append(n)
        is_prime[n] = True

like = []
for p in primes:
    if p == 3:
        like.append(p)
        continue
    q = (p+1)//2
    if is_prime[q]:
        like.append(p)

for l, r in LR:
    ans = bisect_right(like, r) - bisect_left(like, l)
    print(ans)

Solution (Python):
from itertools import accumulate

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

primes = set(range(2, maxr + 1))
for i in range(2, int(maxr ** 0.5 + 1)):
    primes.difference_update(range(i * 2, maxr + 1, i))
c = [0]*((maxr+1) // 2)
for p in primes:
    if p <= (maxr + 1) // 2:
        c[p - 1] = 1
likes = [0]*maxr
for p in primes:
    if p != 2 and c[(p+1) // 2 - 1] == 1:
        likes[p-1] = 1
likes = list(accumulate(likes))
for i in range(Q):
    if LR[i][0] == 1:
        print(likes[LR[i][1] - 1])
    else:
        print(likes[LR[i][1] - 1] - likes[LR[i][0] - 2])

Solution (Python):
class erat():
    def __init__(self,n):
        self.d = set()
        self.prime = set()
        for i in range(2,n+1):
            ind = 2
            if i not in self.d:
                self.prime.add(i)
            while(True):
                temp = i*ind
                ind += 1
                if temp > n:
                    break
                else:
                    if temp not in self.d:
                        self.d.add(temp)
    def isprime(self,n):
        if n in self.prime:
            return True
        else:
            return False

e = erat(10**5)
arr = [0 for i in range(10**5+1)]
for i in range(3,10**5+1):
    if e.isprime(i) and e.isprime((i+1)//2):
        arr[i] = arr[i-1]+1
    else:
        arr[i] = arr[i-1]

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

Solution (Python):
def Eratosthenes(n):
    prime_list = [True for _ in range(n + 1)]
    prime_list[0] = False
    prime_list[1] = False
    for j in range(4, n + 1, 2):
        prime_list[j] = False
    prime_list[2] = True
    for i in range(3, int(n ** 0.5) + 1, 2):
        if prime_list[i]:
            for j in range(i * 2, n + 1, i):
                prime_list[j] = False
    return prime_list


def prime_2017(prime_list):
    prime_2017_list = [True for _ in range(len(prime_list))]
    for i in range(len(prime_list)):
        if i <= 2:
            prime_2017_list[i] = False
        elif prime_list[i]:
            if not prime_list[(i + 1) // 2]:
                prime_2017_list[i] = False
        else:
            prime_2017_list[i] = False
    return prime_2017_list

q = int(input())
num_list = []
num_max = 0
for _ in range(q):
    l, r = map(int, input().split())
    num_list.append([l, r])
    num_max = max(r, num_max)
prime_list = Eratosthenes(num_max)
prime_2017_list = prime_2017(prime_list)
prime_num = [0 for _ in range(num_max + 1)]
for i in range(num_max):
    prime_num[i + 1] = prime_num[i] + prime_2017_list[i + 1]

for l, r in num_list:
    print(prime_num[r] - prime_num[l - 1])

Solution (Python):
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        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 = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
 
K = max(r)
prime = prime(K)
a = [1]*(K+1)
s = [0]*(K+1)
a[0] = 0
a[1] = 0
for i in range(2,K+1):
    if a[i]:
        for j in range(i*i, K+1, i):
            a[j] = 0

for i in range(3,K+1,2):
    if a[i] and a[(i+1)//2]:
        s[i] = 1

for i in range(K):
    s[i+1] += s[i]

for i in range(Q):
    rr, ll = r[i], l[i]
    if rr == ll:
        if s[ll]-s[ll-2] == 1:
            print(1)
        else:
            print(0)
    else:
        print(s[rr] - s[ll-1])

Solution (Python):
def get_isPrime(n):         
    isprime=[1]*(n+1)
    isprime[0]=0
    isprime[1]=0
    for i in range(2, int(n**0.5)+1):
        if not isprime[i]:
            continue
        for j in range(i*2, n+1, i):
            isprime[j]=0
    return isprime

max_n=100000
isprime=get_isPrime(max_n)

ruiseki=[]
for i in range(max_n+1):
    if i==0 or i==1 or i==2:
        ruiseki.append(0)
    else:
        if i%2==0:
            ruiseki.append(ruiseki[i-1])
        else:
            if isprime[i] and isprime[int((i+1)/2)]:
                ruiseki.append(ruiseki[i-1]+1)
            else:
                ruiseki.append(ruiseki[i-1])

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    print(ruiseki[right]-ruiseki[left-1])

Solution (Python):
from collections import deque
from bisect import bisect
ref=deque([2])
refref=deque()
for i in range(3,100000,2):
	flag=1
	for j in range(2,int(i**0.5)+1):
		if i%j==0:
			flag=0
			break
	if flag:
		ref.append(i)
for p in ref:
	if (p+1)//2 in ref:
		refref.append(p)
q,*li=map(int,open(0).read().split())
for l,r in zip(li[::2],li[1::2]):
	print(bisect(refref,r+1)-bisect(refref,l-1))

Solution (Python):
count = int(input())
params = []

for i in range(count):
    params.append(tuple(map(int, input().split())))

maxNum = max(params, key= lambda n : n[1])

sosuList = [1] * (maxNum[1] + 1)
sosuList[0] = 0
sosuList[1] = 0

for i in range(2, len(sosuList)):
    if sosuList[i] == 1:
        for j in range(i + i, len(sosuList), i):
            sosuList[j] = 0

ruisekiwaList = [0] * (len(sosuList) + 1)

for i in range(2, len(sosuList)):
    ruisekiwaList[i + 1] = ruisekiwaList[i] 
    if sosuList[i] == 1 and sosuList[int((i + 1) /2)] == 1:
        ruisekiwaList[i + 1] += 1

for tup in params:
    minNum, maxNum = tup
    result = ruisekiwaList[maxNum + 1] - ruisekiwaList[minNum]
    print(result)

Solution (Python):
def isPrime(x):
  for i in range(2, int(x**0.5)+1):
    if x % i == 0:
      return False
  return True

dp = [0] * 10**5
for i in range(3, 10**5, 2):
  if isPrime(i) and isPrime((i+1)//2):
    dp[i] = dp[i-2] + 1
  else:
    dp[i] = dp[i-2]

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

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



Q = I()
l,r = Line(Q)

def is_prime_all(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

prime_judge = is_prime_all(10**5)

a = []
for i in range(10**5):
  if i==0 or i==1 or i==2:
    a.append(0)
  else:
    if i%2==0:
      a.append(a[-1])
    else:
      if (prime_judge[i]==True) and (prime_judge[(i+1)//2]==True):
        a.append(a[-1]+1)
      else:
        a.append(a[-1])

for i in range(Q):
  print(a[r[i]]-a[l[i]-1])

Solution (Python):




MAX_N = 10 ** 5 + 10 

def primes(n):
    import math
    count_lst = [0] * (n + 1)
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 1):
        if not is_prime[i]: 
            count_lst[i] = count_lst[i - 1]
            continue
        
        if i != 2 and is_prime[(i + 1)//2]: 
            count_lst[i] = count_lst[i - 1] + 1
        else: 
            count_lst[i] = count_lst[i - 1]
        
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    
    for i in range(int(math.sqrt(n)) + 1, n + 1):
        if is_prime[i] and is_prime[(i + 1)//2]: 
            count_lst[i] = count_lst[i - 1] + 1
        else:
            count_lst[i] = count_lst[i - 1]

    return count_lst
    

count_lst = primes(MAX_N)


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

Solution (Python):


N = 10 ** 5 + 10
def primes(n):
    import math
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 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_lst = primes(N)

count_lst = [0] * (N + 1)

def check(n):
    if n%2 == 0:
        return False
    if not n  in prime_lst:
        return False
    if not ((n + 1)//2) in prime_lst:
        return False
    return True


for i in range(3, N + 1):
    if check(i):
        count_lst[i] = count_lst[i - 1] + 1
    else:
        count_lst[i] = count_lst[i - 1]



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

Solution (Python):
Q = int(input())
LR = [list(map(int,input().split())) for _ in [0]*Q]

N = max(r for l,r in LR)

p = []
for i in range(3,N+1,2):
    for j in p:
        if i%j==0: break
        if j*j>i:
            p.append(i)
            break
    else:
        p.append(i)
p.append(2)
p = set(p)

c = [0]*(N+1)
for i in p:
    if (i+1)//2 in p:c[i] = 1

class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

Sc = cumulative_sum(c)

for l,r in LR:
    print(Sc.get(l,r+1))

Solution (Python):
import numpy as np

q = int(input())


is_prime = np.ones(100001, dtype=int)
is_prime[0]=0
is_prime[1]=0

for i in range(2,100001):
    if is_prime[i]==1:
        j=i+i
        while j <= 100000:
            is_prime[j] = 0
            j += i

like2017 = [1 if is_prime[i] and is_prime[(i+1)//2] else 0 for i in range(0,100001) ]

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

Solution (Python):
import numpy as np

q = int(input())


is_prime = np.ones(100001, dtype=int)
is_prime[0]=0
is_prime[1]=0

for i in range(2,100001):
    if is_prime[i]==1:
        j=i+i
        while j <= 100000:
            is_prime[j] = 0
            j += i

like2017 = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,100001)]

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

Solution (Python):
import numpy as np
n=123456
q = int(input())
 
is_prime = np.ones(n+1,dtype=int)
is_prime[0]=0
is_prime[1]=0
 
for i in range(2,n+1):
    if(is_prime[i]==1):
        j=i+i
        while j <= n:
            is_prime[j] = 0
            j += i
 
cnt = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,n+1)]
 
for i in range(1,n+1):
    cnt[i]+=cnt[i-1]
 
for i in range(q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])

Solution (Python):



import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

is_prime = [1]*(10**5+1)
is_prime[0] = 0
is_prime[1] = 0
for i in range(2,10**5+1):
    for j in range(i*2,10**5+1,i):
        is_prime[j] = 0

ansprime = [float('inf')]*(10**5)
for i in range(1,10**5+1,2):
    if is_prime[i] and is_prime[(i+1)//2]:
        ansprime[i] = i
ansprime.sort()
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    li = bisect.bisect_left(ansprime,l)
    ri = bisect.bisect_right(ansprime,r)
    print(ri-li)

Solution (Python):



import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7


def get_prime(n):
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,n+1):
        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 = get_prime(10**5)
ansprime = [float('inf')]*(10**5)
for i in range(1,10**5+1,2):
    if i not in prime:
        continue
    if (i+1)//2 not in prime:
        continue
    ansprime[i] = i
ansprime.sort()
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    li = bisect.bisect_left(ansprime,l)
    ri = bisect.bisect_right(ansprime,r)
    print(ri-li)

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math





 
def main():
    Q = int(input())
    lr = []
    for i in range(Q):
        l, r = map(int,input().split())
        lr.append((l,r))
        
    mapd = []
    for i in range(0, 100001):
        if i == 0:
            mapd.append(0)
            continue
        if i == 1:
            mapd.append(0)
            continue
        if i % 2 == 0:
            mapd.append(mapd[i-1])
            continue
        if is_prime(i) and is_prime((i+1)/2):
            mapd.append(mapd[i-1] + 1)
        else:
            mapd.append(mapd[i-1])
            
        
    for i in lr:
        l, r = i
        print(mapd[r] - mapd[l-1])
    
def is_prime(n): 
    i = 2
    while i * i <=n:
        if n % i == 0:
            return False
        i += 1
    return True
	
if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.readline
q = int(input())
fact = [1]*(10**5+7)
fa_sum = [0]*(10**5+7)
fact[0] = 0
fact[1] = 0

for i in range(2,10**5+7):
  if fact[i]:
    for j in range(i*2,10**5+7,i):
      fact[j] = 0
  if fact[i] and fact[(i+1)//2]:
    fa_sum[i] = fa_sum[i-1] + 1
  else:
    fa_sum[i] = fa_sum[i-1]

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

Solution (Python):
from sys import stdin
from itertools import accumulate
q = int(stdin.readline().rstrip())
l_r = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
max_n = 0
for s in l_r:
    max_n = max(s[1], max_n)



b = [1] * (max_n+1)
b[0] = 0
b[1] = 0

for i in range(2,max_n+1):
    if b[i]:
        j = i*2
        while j <= max_n:
            b[j] = 0
            j += i

c = [1 if x == 1 and b[int((i+1)/2)] == 1 else 0 for i,x in enumerate(b)] 

s = list(accumulate(c))


for i in range(q):
    print(s[l_r[i][1]]-s[l_r[i][0]-1])

Solution (Python):
from sys import stdin
from itertools import accumulate
q = int(stdin.readline().rstrip())
l_r = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
max_n = 0
for s in l_r:
    max_n = max(s[1], max_n)



a = [i for i in range(max_n+1)]

def isPrime(num):
    if num == 0 or num == 1:
        return False
    ans = True
    for i in range(2,int(num/2)+1):
        if num % i == 0:
            ans = False
            break
    return ans
b = [1] * (max_n+1)
b[0] = 0
b[1] = 0
for i in range(2,max_n+1):
    if b[i]:
        j = i*2
        while j <= max_n:
            b[j] = 0
            j += i

c = [1 if x == 1 and b[int((i+1)/2)] == 1 else 0 for i,x in enumerate(b)] 

s = list(accumulate(c))


for i in range(q):
    print(s[l_r[i][1]]-s[l_r[i][0]-1])

Solution (Python):


import sys

sys.setrecursionlimit(10**7)


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h(typ) if m > 1 else typ(input()) for _ in range(n)]


def main():
    q, = read_h()
    rng = read_v(q, m=2)

    MAX = 100000

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

    
    a = [0] * (MAX + 1)
    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] * (MAX + 1)
    for i in range(MAX):
        s[i + 1] = s[i] + a[i]

    
    for l, r in rng:
        print(s[r + 1] - s[l])


if __name__ == '__main__':
    main()

Solution (Python):


import sys
import math
from itertools import chain

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

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())
a = [list(map(int, input().split())) for _ in range(Q)]
s = []
min_num = min(list(chain.from_iterable(a)))
max_num = max(list(chain.from_iterable(a)))
ctr = 0

for j in range(min_num, max_num + 1, 2):
    if is_prime(j) and is_prime((j + 1) // 2):
        s.append(j)

for i in range(Q):
    for k in s:
        if k >= a[i][0] and k <= a[i][1]:
            ctr += 1
    print(ctr)
    ctr = 0

Solution (Python):


import sys
import math
from itertools import chain

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

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())
a = [list(map(int, input().split())) for _ in range(Q)]
s = []
min_num = min(list(chain.from_iterable(a)))
max_num = max(list(chain.from_iterable(a)))
ctr = 0

for j in range(min_num, max_num + 1, 2):
    if is_prime(j) and is_prime((j + 1) // 2):
        s.append(j)

for i in range(Q):
    for k in s:
        if k >= a[i][0] and k <= a[i][1]:
            ctr += 1
    print(ctr)
    ctr = 0

Solution (Python):
import math
q = int(input())
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

r_max = max(r) + 10
is_prime = [True] * (r_max+1)
is_prime[0] = is_prime[1] = False
for i in range(2, r_max):
    if is_prime[i]:
        for j in range(2, r_max // i + 1):
            is_prime[i*j] = False


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


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

Solution (Python):
from itertools import accumulate
from math import sqrt
from sys import stdin
MIN, MAX = 10**5+1, 0

def is_prime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False

    i = 3
    while i <= sqrt(x):
        if x % i == 0:
            return False
        i = i + 2
    
    return True

Q = int(stdin.readline().rstrip())

LR = []
for i in range(Q):
    l, r = [int(_) for _ in stdin.readline().rstrip().split()]
    if l < MIN:
        MIN = l
    if r > MAX:
        MAX = r
    LR.append((l, r))

primes = [is_prime(i) and is_prime((i+1)//2) for i in range(MIN, MAX+1)]
primes = [0]+primes
primes = list(accumulate(primes))

for i in range(Q):
    print(primes[LR[i][1] - MIN+1] - primes[LR[i][0] - MIN])

Solution (Python):
def is_prime(n):
    if n < 2:
        return 0

    if n == 2:
        return 1

    if n % 2 == 0:
        return 0

    i = 3
    while i * i <= n:
        if n % i == 0:
            return 0
        i += 2

    return 1


A = [is_prime(i) for i in range(1 + 10 ** 5)]
S = [A[i] & A[(i + 1) // 2] for i in range(1 + 10 ** 5)]
T = [0] * (1 + 10 ** 5)
T[0] = S[0]
for i in range(1, 1 + 10 ** 5):
    T[i] = T[i - 1] + S[i]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(T[r] - T[l - 1])

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

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

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

for a in range(2,10**5 + 9):
    if prime[a] and prime[int((a+1)/2)]:
        Ans[a] = 1
    Ans[a] += Ans[a-1]

for l,r in LR:
    print(Ans[r]-Ans[l-1])

Solution (Python):
def shave(n):
    n_root = int(n**0.5)
    candidate = [i for i in range(3,n+1,2)]
    for i in range(3,n_root+2,2):
        candidate = [ j for j in candidate if j == i or j % i != 0]   
    candidate = [2] + candidate
    return candidate


def cumsum(inlist):
    s = 0
    outlist = []
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist

prime_list = shave(100000)

prime_or_not_prime_list = [ 0 for i in range(10**5+1) ]
like_2017_list = [ 0 for i in range(10**5+1) ]
for i in prime_list:
    prime_or_not_prime_list[i] = 1
    j = (i + 1) // 2
    if prime_or_not_prime_list[j] == 1:
        like_2017_list[i] = 1
like_2017_list_sum = cumsum(like_2017_list)


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

Solution (Python):
def sieve(N):
    global table,prime
    table = [True]*(N+1)
    table[0] = False
    table[1] = False
    prime = []
    for i in range(2,N+1):
        if table[i]:
            prime.append(i)
            for j in range(2*i,N+1,i):
                table[j] = False

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r+1] - cs[l]

Q = int(input())

sieve(10**5)

def judge(x):
    return x % 2 and table[x] and table[(x+1)//2]

flag = [judge(x) for x in range(0,10**5+1)]

accmulate(flag)

ans_list = []

for _ in range(Q):
    l,r = map(int,input().split())
    ans = query(l,r+1)
    ans_list.append(ans)

print(*ans_list, sep="\n")

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

def main():
    q=int(input())
    is_prime = primes(10**5+1)
    a = [0 for i in range(10**5+1)]
    for i in range(3,10**5+1):
        if is_prime[i] and is_prime[(i+1)//2]:a[i]+=1
    for i in range(3,10**5+1):a[i]+=a[i-1]
    for i in range(q):
        l,r=map(int,input().split())
        print(a[r]-a[l-1])

main()

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

def main():
    q=int(input())
    is_prime = primes(10**5+1)
    a = [0 for i in range(10**5+1)]
    for i in range(3,10**5+1):
        if is_prime[i] and is_prime[(i+1)//2]:
            a[i]+=1

    for i in range(3,10**5+1):
        a[i]+=a[i-1]

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

main()

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

def main():
    q=int(input())
    is_prime = primes(10**5+1)
    a = [0 for i in range(10**5+1)]
    for i in range(3,10**5+1):
        if is_prime[i] and is_prime[(i+1)//2]:
            a[i]=a[i-1]+1
        else:
            a[i]=a[i-1]

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

main()

Solution (Python):
from itertools import accumulate
Q = int(input())

def sieve(n):
    if n == 0:
        return [False]

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

MAX = 10 ** 5
is_prime = sieve(MAX)
cnt = [0] * (MAX + 1)
for i in range(MAX + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        cnt[i] = 1
cnt = list(accumulate(cnt))

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

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

sosuu=[2]
s=sosuu.append
for i in range(1,50001):
	k=2*i+1
	for j in sosuu:
		if k%j==0:
			break
		elif j>320:
			s(k)
			break
	else:
		s(k)

sosuu2=set(sosuu)
num=[]
n=num.append
for i in sosuu:
	k=(i+1)//2
	if k in sosuu2:
		n(i)

lis=[0]*100000

for i in num:
	lis[i-1]=1
	
from itertools import accumulate
lis=[0]+list(accumulate(lis))

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

Solution (Python):
from itertools import accumulate
Q = int(input())

def prime(n):
    
    
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5+1)):
        primes.difference_update(range(i*2, n+1, i))
    primes=list(primes)
    return primes

prime_set = set(prime(10**5))
ans = []

for i in range(10**5+1):
    if i%2 == 0:
        ans.append(0)
    else:
        if i in prime_set and (i+1)//2 in prime_set:
            ans.append(1)
        else:
            ans.append(0)
ans = list(accumulate(ans))

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

Solution (Python):
q=int(input())
LR=[[int(i) for i in input().split()] for _ in range(q)]
sosu=[False]*(10**5+1)
question=[0]*(10**5+1)
for i in range(2,10**5+1):
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            break
    else:
        sosu[i]=True
for i in range(3,10**5+1):
    if sosu[i] and sosu[(i+1)//2]:
        question[i]=1
for i in range(1,10**5+1):
    question[i]+=question[i-1]
for l,r in LR:
    print(question[r]-question[l-1])

Solution (Python):
max_num = 10**5+5
eratos_thenes_sieve = [0,0] + [1]*max_num
n = 2 
while n*n <= max_num:
  if eratos_thenes_sieve[n]:
    for i in range(2*n, max_num, n):
      eratos_thenes_sieve[i] = 0
  n += 1
  
isLike2017 = [0] * max_num
cumulativeSums = [0]
for i in range(max_num):
  if eratos_thenes_sieve[i] and eratos_thenes_sieve[(i+1)//2]:
    isLike2017[i] = 1
  cumulativeSums.append(cumulativeSums[-1] + isLike2017[i])
  
  
q = int(input())

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

Solution (Python):
def sieve(n):
    prime=[]
    is_prime=[True]*(n+1)
    is_prime[0]=False
    is_prime[1]=False
    for i in range(2,n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(2*i,n+1,i):
                is_prime[j]=False
    return is_prime
prime=sieve(10**5)
prime1=[False]*(10**5+1)
for i in range(10**5+1):
    if prime[i]:
        if 1<=i*2-1<=10**5:
            prime1[i*2-1]=True
prime2=[0]*(10**5+1)
for i in range(10**5+1):
    if prime[i] and prime1[i]:
        prime2[i]=1
Sum=[0]*(10**5+1)
for i in range(1,10**5+1):
    Sum[i]=Sum[i-1]+prime2[i]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(Sum[r]-Sum[l-1])

Solution (Python):



arr = [0 for _ in range(10 ** 5 + 1)]


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


for i in range(3, 10**5+1):
    if isPrime(i) and isPrime(int((i + 1) / 2)):
        arr[i] = 1
    arr[i] += arr[i-1]

q = int(input())


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