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):
from math import sqrt, ceil

cache = {3}
primes = {2,3}
def isprime(n):
    if n in primes:
        return True
    for i in range(3, ceil(sqrt(n))+1, 2):
        if n % i == 0:
            return False
    primes.add(n)
    return True

def prepare():
    l = 5
    r = 10**5-1
    for n in range(l, r+1, 4):
        if n in cache:
            continue
        m = (n - 1) // 2
        if isprime(m+1) and isprime(n):
            cache.add(n)

def solve(l, r):
    cnt = 0
    if l <= 3 <= r:
        cnt = 1
        l = 5
    if l % 4 == 3:
        l += 2
    for n in range(l, r+1, 4):
        if n in cache:
            cnt += 1
            continue
        m = (n - 1) // 2
        assert n % 4 == 1
        if isprime(m+1) and isprime(n):
            cache.add(n)
            cnt += 1
    return cnt

def main():
    global cache
    from bisect import bisect_left, bisect_right
    cache = sorted(cache)
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        i = bisect_left(cache, l)
        j = bisect_right(cache, r)
        print(j-i)

prepare()
main()

Solution (Python):
import math
import bisect

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


if __name__ == '__main__':
    data = set(get_sieve_of_eratosthenes(100000))
    pos = []
    for i in data:
        if (i + 1) % 2 == 0:
            if (i + 1) // 2 in data:
                pos.append(i)
    pos.sort()
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        print(bisect.bisect_right(pos,r) - bisect.bisect_left(pos,l))

Solution (Python):
table_prime_numbers = [True for _ in range(10 ** 5)]
table_2017_numbers = [0 for _ in range(10 ** 5)]
table_2017_numbers_acm = [0 for _ in range(10 ** 5)]

def init_tables():
  table_prime_numbers[0] = table_prime_numbers[1] = False
  for i in range(2, 10 ** 5):
    if table_prime_numbers[i]:
      for j in range(i * 2, 10 ** 5, i):
        table_prime_numbers[j] = False
      if table_prime_numbers[(i + 1) // 2]:
        table_2017_numbers[i] = 1
  
  for i in range(2, 10 ** 5):
    table_2017_numbers_acm[i] = table_2017_numbers_acm[i - 1] + table_2017_numbers[i]
      
  return

def cumul(n):
  return table_2017_numbers_acm[n]

def result(l, r):
  return cumul(r) - cumul(l - 1)

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

  return

if __name__ == "__main__":
  init_tables()
  main()

Solution (Python):
import math


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


if __name__ == '__main__':
    data = set(get_sieve_of_eratosthenes(100000))
    pos = []
    for i in data:
        if (i + 1) % 2 == 0:
            if (i + 1) // 2 in data:
                pos.append(i)
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        ans = 0
        for i in pos:
            if i <= r and l <= i:
                ans += 1
        print(ans)

Solution (Python):
table_prime_numbers = [True for _ in range(10 ** 5)]
table_2017_numbers = [False for _ in range(10 ** 5)]
table_2017_numbers_acm = [0 for _ in range(10 ** 5)]

def init_tables():
  table_prime_numbers[0] = table_prime_numbers[1] = False
  for i in range(2, 10 ** 5):
    if table_prime_numbers[i]:
      for j in range(i * 2, 10 ** 5, i):
        table_prime_numbers[j] = False
        
  for i in range(2, 10 ** 5):
    if table_prime_numbers[i]:
      if (i * 2 - 1 < 10 ** 5) and table_prime_numbers[i * 2 - 1]:
        table_2017_numbers[i * 2 - 1] = True
  
  for i in range(2, 10 ** 5):
    table_2017_numbers_acm[i] = table_2017_numbers_acm[i - 1] + int(table_2017_numbers[i])
      
  return

def cumul(n):
  return table_2017_numbers_acm[n]

def result(l, r):
  return cumul(r) - cumul(l - 1)

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

  return

if __name__ == "__main__":
  init_tables()
  main()

Solution (Python):
import math

def main():

    Q = int(input())
    query = []
    max_r = 0
    for _ in range(Q):
        l, r = map(int, input().split())
        query.append([l, r])
        max_r = max(max_r, r)

    primes = set()
    for i in range(2, max_r+1):
        if isprime(i):
            primes.add(i)

    
    count = [0]
    for i in range(1, max_r+1):
        if i % 2 == 1 and i in primes and (i+1) // 2 in primes:
            count.append(count[-1] + 1)
        else:
            count.append(count[-1])

    
    for l, r in query:
        print(count[r] - count[l-1])


def isprime(n):
    if n == 1: return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

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

def main():
    Q = int(input())
    N = 10 ** 5
    num_list = [0] * (N + 5)

    for i in range(1,N+1):
        if is_prime(i) and is_prime((i+1)//2):
            num_list[i] = 1

    sum_num = [0] * (N + 6)

    for i in range(1,N+2):
        sum_num[i+1] = sum_num[i] + num_list[i]

    sum_num.pop(0)

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



main()

Solution (Python):

import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
sys.setrecursionlimit(200000)





input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()


def isPrime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

from copy import deepcopy
class CumulativeSum():
    def __init__(self, arr: list):
        self.data = deepcopy(arr)
        for i in range(1, len(self.data)):
            self.data[i] += self.data[i - 1]

    def _query(self, k: int) -> int:
        """[0,k]の和"""
        if k < 0:
            return 0
        else:
            return self.data[min(k, len(self.data) - 1)]

    def query(self, l: int, r: int) -> int:
        """[l,r)の和"""
        if l > r:
            return 0
        else:
            return self._query(r - 1) - self._query(l - 1)

    def __str__(self):
        return str(self.data)
    def __getitem__(self, k):
        return self.data[k]

def isOK(n):
    return n > 2 and isPrime(n) and isPrime((n + 1) / 2)

def main():
    Q = ii()
    v = [0] * 100001
    for i in range(100000 + 1):
        if isOK(i):
            v[i] = 1
    c = CumulativeSum(v)
    for i in range(Q):
        l, r = mi()
        print(c.query(l, r + 1))
    return


if __name__ == '__main__':
    main()

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

def get_like_2017(N):
  nums = set([i for i in range(2,N+1)])
  for i in range(2, int(math.sqrt(N))+1):
    for j in range(2,int(N//i)+1):
      if i*j in nums: nums.remove(i*j)
  
  nums_like_2017 = set([])
  for num in nums:
    if is_prime(int((num+1)/2)) is True:  nums_like_2017.add(num)
  return nums_like_2017

nums_like_2017 = sorted(list(get_like_2017(10**5)))

Q = int(input())
for _ in range(Q):
  l,r = map(int, input().split())
  idx_l = bisect.bisect_left(nums_like_2017, l)
  idx_r = bisect.bisect_right(nums_like_2017, r)
 
  print(idx_r-idx_l)

Solution (Python):
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def conb(n,r): return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
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 = inp()
L = [0] * q
R = [0] * q
for i in range(q):
    L[i],R[i] = inpl()
    L[i] = (L[i]+1)//2
    R[i] = (R[i]+1)//2

cnt = [0] * ((10**5+10)//2)
for i in range(1,(10**5+5)//2):
    if is_prime(i) and is_prime(i+i-1):
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]
for i in range(q):
    print(cnt[R[i]] - cnt[L[i]-1])

Solution (Python):
from bisect import bisect_left

Q = int(input())

prime = [2, 3]
for i in range(5, 10 ** 5 + 1, 2) :
    flg = True
    for p in prime :
        if p * p > i :
            break
        if i % p == 0 :
            flg = False
            break
    if flg :
        prime.append(i)
        
like2017 = []
for p in prime :
    if (p + 1) // 2 in prime :
        like2017.append(p)
        
for _ in range(Q) :
    l, r = map(int, input().split())
    print(bisect_left(like2017, r + 1) - bisect_left(like2017, l))

Solution (Python):

MAX = 101010

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


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


MAX = 101010
a=[0]*MAX
for i in range(MAX+1):
    if i%2 == 0:
        continue
    elif 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 i in range(Q):
    print(s[r[i] + 1] - s[l[i]])

Solution (Python):


input=open(0).readline
q=int(input())

lr=[]
mxr=0

for i in range(q):
    l,r=map(int,input().split())
    lr.append((l,r))
    mxr=max(mxr,r)

def sieve(n):
    end=int(pow(n,0.5))+1
    is_prime=[True]*(n+1)
    is_prime[0]=False
    is_prime[1]=False

    for i in range(2,end+1):
        if not is_prime[i]:continue
        for j in range(i*2,n+1,i):
            is_prime[j]=False
    return is_prime

prime=sieve(mxr)

x=[0]
cnt=0
for i in range(1,mxr+1):
    if prime[i]&prime[(i+1)//2]:
        cnt+=1
    x.append(cnt)
for l,r in lr:
    print(x[r]-x[l-1])

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    Q = int(input())
    lr = [list(map(int, input().split())) for i in range(Q)]

    MAX = int(1e5)
    MAX_PRIME = MAX
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    count = [0] * (MAX+1)
    for p in primes:
        if p&1:
            tmp = (p + 1) // 2
            if is_prime[tmp]:
                count[p] = 1
    for i in range(1, MAX+1):
        count[i] += count[i-1]
    
    
    for i in range(Q):
        l, r = lr[i]
        print(count[r] - count[l-1])
    



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



Q = int(input())

slis = primes(10 ** 5)
sdic = {}

for i in slis:
    sdic[i] = 1



"""
for i in range(10 ** 5 - 2):

    i += 3

    flag = True

    for j in sdic:
        if i % j == 0:
            flag = False

    if flag:
        sdic[i] = 1



"""

adic = {}
adic[-1] = 0
for j in range(10 ** 5 // 2):

    now = 1 + j * 2

    if now in sdic and (now + 1) // 2 in sdic:
        adic[now] = adic[now-2] + 1

    else:
        adic[now] = adic[now-2]

for i in range(Q):

    l,r = map(int,input().split())

    print (adic[r] - adic[l-2])

Solution (Python):
from bisect import*
p=[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]
for _ in [0]*int(input()):
 l, r = map(int, input().split())
 print(bisect_right(p, r)-bisect_left(p, l))

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

L=[0]*(10**5+1)
cnt=0
for i in range(3,10**5+1):
    if is_prime(i) and is_prime((i+1)//2):
        cnt+=1
    L[i]=cnt

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

Solution (Python):
Q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(Q)]
primes = [2]
MAX = 10**5
p_list = [0] * (MAX+1)
cnt = 0
for i in range(3, MAX+1):
  is_prime = True
  likely = False
  for prime in primes:
    if i%prime == 0:
      is_prime = False
      break
    if (i+1)//2 == prime:
      likely = True
      break
    elif (i+1)//2 < prime:
      break
    else:
      continue
  if is_prime:
    primes.append(i)
    if likely:
      cnt += 1
  p_list[i] = cnt

for l, r in queries:
  if p_list[l] > p_list[l-1]:
    print(p_list[r]-p_list[l]+1)
  else:
    print(p_list[r]-p_list[l])

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

q=int(input())
lr=[tuple(map(int, input().split())) for _ in range(q)]
is_primes=makeIsPrimeList(10**5)
mylst=[0]*(10**5+1)
cnt=0
for i in range(len(mylst)):
  if is_primes[i] and is_primes[(i+1)//2]:
    cnt+=1
  mylst[i]=cnt
for l, r in lr:
  print(mylst[r]-mylst[l-1])

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    pl = {}
    p = [True] * (10 ** 5 + 1)
    p[0] = False
    p[1] = False
    cnt = 0
    pll = [0] * (10 ** 5 + 1)
    for i in range(2, len(p)):
        if p[i]:
            pl[i] = 1
            for j in range(i, len(p), i):
                p[j] = False
        if i % 2 != 0:
            if (i + 1) // 2 in pl and i in pl:
                cnt += 1
        pll[i] = cnt
    q = int(input().rstrip('\n'))
    lr = [list(map(int, input().rstrip('\n').split())) for _ in range(q)]
    for l, r in lr:
        print(pll[r] - pll[l-1])


if __name__ == '__main__':
    slove()

Solution (Python):
import sys
input = sys.stdin.readline
Q = int(input())

LR = []
for _ in range(Q):
    l,r = map(int, input().split())
    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: True for i in range(n + 1) if is_prime[i]}

prime_dict = primes(10**5)
like_2017 = []
for n in prime_dict:
    if (n+1)//2 in prime_dict:
        like_2017.append(n)

like_2017 = list(sorted(like_2017))


from bisect import bisect_left, bisect_right

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    return i

for l, r in LR:
    if l == r:
        if l in like_2017:
            print(1)
        else:
            print(0)
    else:
        l_idx = index(like_2017, l)
        r_idx = index(like_2017, r)
        if r in like_2017:
            r_idx += 1
        print(r_idx-l_idx)

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

def sosuu(x):
  if x == 1:
    return False
  else:
    for i in range(1,int(math.sqrt(x))):
      if x % (i+1) == 0:
        return False
    return True

table=[0]*50001
for i in range(1,50001):
  if sosuu(2*i - 1) and sosuu(i):
    table[i]=table[i-1] + 1
  else:
    table[i]=table[i-1]
    
ans=[0]*Q
for i in range(Q):
  l,r=map(int,input().split())
  ans[i]=table[(r+1)//2] - table[(l+1)//2 - 1]
  
for i in range(Q):
  print(ans[i])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    m = II()
    print(48-m)
    return


def B():
    a, _ = LI()
    s = S()
    ans = list(map(str, range(10)))
    for num, si in enumerate(s):
        if num != a:
            if si in ans:
                continue
            print("No")
            return
        else:
            if si == "-":
                continue
            print("No")
            return
    print("Yes")
    return


def C():
    n = II()
    csf = LIR(n - 1)
    for i in range(n - 1):
        b = 0
        for k in range(i, n - 1):
            c, s, f = csf[k]
            if b <= s:
                b = s + c
            else:
                b += c + (-b % f)
        print(b)
    print(0)
    return


def D_():
    a = II()
    ans = inf
    b = 0
    for _ in range(1, 10 ** 5):
        b += a
        ans = min(ans, sum(list(map(int, list(str(b))))))
    print(ans)
    return

def D():
    q = II()
    def primes(n):
        """ Input n>=6, Returns a list of primes, 2 <= p < n """
        """ 6以上の数であれば p (素数) <= n のlistを返す """
        n, correction = n-n%6+6, 2-(n%6>1)
        sieve = [True] * (n//3)
        for i in range(1,int(n**0.5)//3+1):
            if sieve[i]:
                k=3*i+1|1
                sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
                sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
        return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]
    primelis = primes(10 ** 5)
    d = defaultdict(int)
    for i in primelis:
        d[i] += 1
    dp = [0]
    for i in range(3, 10 ** 5, 2):
        dp.append(dp[-1] + (1 if (d[i] and d[(i + 1) // 2]) else 0))
    for i in range(q):
        l, r = map(lambda x: x // 2, LI())
        if l == 0:
            print(dp[r])
            continue
        print(dp[r] - dp[l - 1])




if __name__ == '__main__':
    D()

Solution (Python):

def prime_table(n):
  list = [True for _ in range(n+1)]
  list[0] = False 
  list[1] = False 
  i = 2
  
  while i**2 <= n:
    if list[i]:
      j = i + i
      while j <= n:
        list[j] = False
        j += i
    i += 1
  table = [i for i in range(n+1) if list[i]]
  return table






def ABC084D(prime_table):
  lst = [3, 5]
  for i in range(len(prime_table)):
    if (prime_table[i] - 1) % 12 == 0:
      if (prime_table[i] + 1) // 2 in prime_table:
        lst.append(prime_table[i])
  return lst


import bisect

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


primes = prime_table(100000) 
lst = ABC084D(primes) 
for i in range(Q):
  ans = bisect.bisect_right(lst,LR[i][1]) - bisect.bisect_left(lst,LR[i][0])
  print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right


def get_primes(n: int) -> list:
    
    n += 1  
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(Q))
    P = get_primes(10 ** 5)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]
    bsr, bsl = bisect_right, bisect_left
    ans = [bsr(selected_P, r) - bsl(selected_P, l) for l, r in A]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right


def get_primes(n: int) -> list:
    
    n += 1  
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(Q))
    P = get_primes(10 ** 5)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]
    ans = []
    bsr, bsl = bisect_right, bisect_left
    for l, r in A:
        x = bsr(selected_P, r) - bsl(selected_P, l)
        ans += [x]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right


def get_primes(n):
    
    n += 1  
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(Q))
    _, R = zip(*A)
    lim = max(R)
    P = get_primes(lim)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]
    ans = []
    for l, r in A:
        x = bisect_right(selected_P, r) - bisect_left(selected_P, l)
        ans += [x]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right


def get_primes(n):
    
    n += 1  
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(Q))
    P = get_primes(10 ** 5)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]
    ans = []
    for l, r in A:
        x = bisect_right(selected_P, r) - bisect_left(selected_P, l)
        ans += [x]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

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

A = [0 for i in range(50000)]
for i in range(1, 50000):
  A[i] = A[i-1]
  if isp(i+1) and isp(2*i+1):
    A[i] += 1
    
Q = int(input())
for i in range(Q):
  r, l = map(int, input().split())
  print(A[l//2]-A[max(0, r//2-1)])

Solution (Python):
import math


def sosu(N):
    tbl = [0] * (N + 1)
    tbl[0] = 1
    tbl[1] = 1
    lim = math.ceil(math.sqrt(N))
    for i in range(2, lim + 1):
        if tbl[i] == 0:
            for j in range(2, N + 1):
                tmp = i * j
                if tmp > N: break
                tbl[tmp] = 1
    return tbl


ptbl = sosu(10 ** 5)

memo = [0] * (10 ** 5 + 1)
for i in range(2, len(memo)):
    memo[i] = memo[i - 1]
    if ptbl[i] == 1: continue
    if ptbl[(i + 1) // 2] == 0:
        memo[i] += 1


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

Solution (Python):
Ps = set()
M = [False]*100001
p = 2
while p <= 100000:
  if not(M[p]):
    Ps.add(p)
    for i in range(p, 100000, p):
      M[i] = True
  p += 1

r = 0
Ss = [0]*100001
for i in range(100000):
  if i%2 == 1 and i in Ps and (i+1)//2 in Ps:
    r += 1
  Ss[i] = r
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  re = Ss[r]-Ss[l-1]
  print(re)

Solution (Python):
import bisect
a = [True] * 100001
a[0] = False
a[1] = False
p = []
for i in range(2, 100001):
    if a[i]:
        for j in range(i * 2, 100001, i):
            a[j] = False
        if i % 2 != 0 and a[(i + 1) // 2]:
            p.append(i)
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(p, r) - bisect.bisect_left(p, l))

Solution (Python):
import numpy as np
import bisect

def prime_number(num):  
  if num == 0 or num == 1:
    return False
  
  if num > 2 and num % 2 == 0:
    return False  
  
  for i in range(3, int(np.sqrt(num)+1)):
    if num % i == 0:
      return False
  
  return True

def check(num):
  if prime_number(num) and prime_number((num+1)//2):
    return True
    
  return False
    
checked = [i for i in range(10**5+1) if check(i)]





q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(checked, r) - bisect.bisect_left(checked, l))