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):
q = int(input())
LR = [0]*q
for i in range(q):
    LR[i] = list(map(int,input().split()))
lis = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317]

p_lis = [0]*(1+10**5)
for i in range(3,10**5+1):
    sw1 = 1
    sw2 = 1
    for P in lis:
        if P > i**0.5:
            break
        if i%P == 0:
            sw1 = 0
            break
        
    if sw1 == 1:
        for P in lis:
            if P > ((i+1)//2)**0.5:
                break
            if (i+1)//2%P == 0:
                sw2 = 0
                break
            
    if sw1 == 1 and sw2 == 1:
        p_lis[i] = 1
s_lis = [0]*(1+10**5)
for i in range(1,len(p_lis)):
    if p_lis[i] == 1:
        s_lis[i] = s_lis[i-1] + 1
    else:
        s_lis[i] = s_lis[i-1]
for L,R in LR:
    print(s_lis[R]-s_lis[L-1])

Solution (Python):
def main():
    import math
    def generate_primes(num):
        if num == 1: return []
        primes = list(range(2, num + 1))
        i, p = 0, 1
        while p <= math.sqrt(num):
            if primes[i] != 0:
                p = primes[i]
                primes = [prime if (prime % p != 0 or prime == p) else 0 for prime in primes]
            i += 1
        return set([p for p in primes if p != 0])

    primes = generate_primes(100000)
    ans = [0] * 50001
    for j in range(1, 50001):
        i = 2 * j - 1
        if i in primes and (i + 1) // 2 in primes:
            ans[j] = ans[j - 1] + 1
        else:
            ans[j] = ans[j - 1]
    q = int(input())
    for _ in range(q):
        l, r = list(map(lambda x: (int(x) + 1) // 2, input().split()))
        print(ans[r] - ans[l - 1])


if __name__ == '__main__':
    main()

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

s = [0] * (100001)
for i in range(1, 10**5+1): 
    if i%2 == 1 and is_prime(i) and is_prime((i+1)//2):
        s[i-1] = 1

lst = [0] * (100001)
for i in range(10**5):
    lst[i+1] = lst[i] + s[i]

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

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

def bisect(lst, isok, ok, ng):
    while(abs(ok-ng)>1):
        mid = (ok+ng)//2
        if isok(lst[mid]):
            ok = mid
        else:
            ng = mid
    return ok

s = []
for i in range(10**5):
    if i%2 == 1 and is_prime(i) and is_prime((i+1)//2):
        s.append(i)

s.sort()

q = int(input())
for k in range(q):
    l, r = map(int, input().split())
    l0 = bisect(s, lambda x:x >= l, len(s), -1)
    r0 = bisect(s, lambda x:x <= r, -1, len(s))
    print(max(0, r0-l0+1))

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue
from decimal import Decimal



sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    
    
    limit = 10 ** 5 + 1
    prime = [False if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 else True for n in range(limit)]
    prime[0] = prime[1] = False
    prime[2] = prime[3] = prime[5] = True
    for p in range(3, limit, 2):
        if math.sqrt(limit) < p:
            break
        for q in range(p ** 2, limit, p):
            prime[q] = False

    
    
    cnt = [0] * limit
    for n in range(len(cnt)):
        if prime[n] and prime[(n + 1) // 2]:
            cnt[n] = 1
    for n in range(1, len(cnt)):
        cnt[n] += cnt[n - 1]

    
    Q = ii()
    for q in range(Q):
        l, r = il()
        print(cnt[r] - cnt[l - 1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal



sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    
    
    limit = 10 ** 5 + 1
    prime = [False if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 else True for n in range(limit)]
    prime[0] = prime[1] = False
    prime[2] = prime[3] = prime[5] = True
    for p in range(3, limit, 2):
        if math.sqrt(limit) < p:
            break
        for q in range(p ** 2, limit, p):
            prime[q] = False

    
    
    cnt = [0]*limit
    for n in range(len(cnt)):
        if prime[n] and prime[(n+1)//2]:
            cnt[n] = 1
    for n in range(1, len(cnt)):
        cnt[n] += cnt[n-1]

    
    Q = ii()
    for q in range(Q):
        l, r = il()
        print(cnt[r]-cnt[l-1])


if __name__ == '__main__':
    main()

Solution (Python):
import math
import bisect
def binary_search(a,n):
    low = 0
    high = len(a) - 1
    while low <= high:
        mid = (low + high) // 2
        index = a[mid]
        if index == n:
            return True
        elif index < n:
            low = mid+1
        else:
            high = mid -1
    return False

def get_sieve_oof_eratosthenes(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]
data = get_sieve_oof_eratosthenes(10**5 + 1)
count = [0 for i in range(10**5+1)]
for i in range(3,10**5,2):
    if binary_search(data,i) and binary_search(data,(i+1)//2):
            count[i] += count[i-1] + 1
            count[i+1] = count[i]
    else:
        count[i] += count[i-1]
        count[i+1] = count[i]
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(count[r]-count[l-1])

Solution (Python):
is_prime = [1]*101010
is_prime[0] = 0
is_prime[1] = 0
max = 101010

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

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

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


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

Solution (Python):
is_prime = [1]*101010
is_prime[0] = 0
is_prime[1] = 0
max = 101010

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

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

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


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

Solution (Python):
import bisect

def sieve(n):
	ret = []
	divlis = [-1]*(n+1)  
	flag = [True]*(n+1)
	flag[0] = False
	flag[1] = False
	ind = 2
	while ind <= n:
		if flag[ind]:
			ret.append(ind)
			ind2 = ind**2
			while ind2 <= n:
				flag[ind2] = False
				divlis[ind2] = ind
				ind2 += ind
		ind += 1
	
	return ret

svl = set(sieve(10**5))
ansl = []

for i in svl:
	if i * 2 - 1 in svl:
		ansl.append(i*2-1)

ansl.sort()

q = int(input())

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

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    q = int(ipt())

    
    def primes(n):
        if n < 4:
            return []
        else:
            pri = [2]
            k = 3
            while k*k <= n:
                for i in pri:
                    if k%i == 0:
                        break
                    elif i == pri[-1]:
                        pri.append(k)
                k += 2
            return pri

    p = primes(10**10)
    sm = [0]*100001
    for pi in p[1::]:
        if (pi+1)//2 in p:
            sm[pi] += 1

    for i in range(100000):
        sm[i+1] += sm[i]

    for _ in [0]*q:
        l,r = map(int,ipt().split())
        print(sm[r]-sm[l-1])

    return


if __name__ == '__main__':
    main()

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

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

def main():
    pl = prime_boolean_table(10**5)
    ql = [0]*(10**5+1)
    for i in range(1,10**5+1):
        if pl[i] and pl[(i+1)//2]:
            ql[i] += 1
    ql = list(itertools.accumulate(ql))
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        print(ql[r]-ql[l-1])

if __name__=='__main__':
    main()

Solution (Python):
import sys
import numpy as np
input = sys.stdin.buffer.readline
Q = int(input())


def is_prime(v):
    for i in range(2, v):
        if i * i > v:
            break
        if v % i == 0:
            return False
    return True


def make_prime(U):
    is_prime = np.zeros(U, np.bool)
    is_prime[2] = 1
    is_prime[3::2] = 1
    M = int(U**.5) + 1
    for p in range(3, M, 2):
        if is_prime[p]:
            is_prime[p * p::p + p] = 0
    return is_prime


is_primes = make_prime(10**5 + 2)


V = [0] * (10**5 + 2)
for i in range(1, len(V)):
    if i % 2 == 0:
        V[i] = V[i - 1]
        continue
    if is_primes[i] and is_primes[(i + 1) // 2]:
        V[i] = V[i - 1] + 1
    else:
        V[i] = V[i - 1]


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

Solution (Python):
import bisect
import sys

input = sys.stdin.readline


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
    N = 100001
    prime = []
    for i in range(3, N):
        tmp = prime_factorize(i)
        if len(tmp) == 1:
            prime.append(i)
    
    primes = []
    for p in prime:
        k = (p+1)//2
        tmp = prime_factorize(k)
        if len(tmp) == 1:
            primes.append(p)

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

if __name__ == "__main__":
    main()

Solution (Python):
import math

n = int(input())
a = 0
li = [] 
ans = []

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

for i in range(10**5//2):
    x = 2*i+1
    y = i+1
    if is_prime(y):
        if is_prime(x):
            a += 1
    li.append(a)

for i in range(n):
    l, r = map(int,input().split())
    ans.append(li[r//2]-li[max(0,l//2-1)])

for i in ans:
    print(i)

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]


Q = int(input())
ls = [0]
prime = set(get_sieve_of_eratosthenes(10**5 + 10))

output = []
for i in range(10**5+10):
    if (i in prime) & (int((i+1)/2) in prime):
        ls.append(ls[-1]+1)
    else: 
        ls.append(ls[-1])

for q in range(Q):
    l, r = map(int, input().split())
    output.append(ls[r+1]-ls[l])
print(*output, sep="\n")

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]


Q = int(input())
ls = [0]
prime = set(get_sieve_of_eratosthenes(10**5 + 10))

output = []
for i in range(1, 10**5+1):
    if (i in prime) & (int((i+1)/2) in prime):
        ls.append(ls[i-1]+1)
    else: ls.append(ls[i-1])

for q in range(Q):
    l, r = map(int, input().split())
    output.append(ls[r]-ls[l-1])
print(*output, sep="\n")

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]


Q = int(input())
ls = [0]
prime = set(get_sieve_of_eratosthenes(10**5 + 10))

output = []
for i in range(1, 10**5+1):
    if (i in prime) & (int((i+1)/2) in prime):
        ls.append(ls[i-1]+1)
    else: ls.append(ls[i-1])

for q in range(Q):
    l, r = map(int, input().split())
    output.append(ls[r]-ls[l-1])
print(*output, sep="\n")

Solution (Python):
import bisect, math
N = 10**5
Q = int(input())

lst1 = [2]
for L in range(3, N, 2):
  f = 0
  for d in range(3, math.floor(math.sqrt(L))+1, 2):
    if L % d == 0:
      f = 1
      break
  if f == 0:
    lst1.append(L)

lst1 = set(lst1) 
lst2 = [i for i in lst1 if (i+1)//2 in lst1]

lst2.sort()

for _ in range(Q):
  l, r = map(int, input().split())
  a = bisect.bisect_left(lst2, l)
  b = bisect.bisect_right(lst2, r)
  print(b-a)

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, open(0).read().split())
    ans = []
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(A[r] - A[l - 1])

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, open(0).read().split())
    ans = []
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(A[r] - A[l - 1])

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, open(0).read().split())
    ans = []
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(A[r] - A[l - 1])

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, open(0).read().split())
    ans = []
    for l, r in zip(LR[::2], LR[1::2]):
        ans.append(A[r] - A[l - 1])

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [n in primes and (n + 1) // 2 in primes for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, open(0).read().split())
    ans = []
    for l, r in zip(LR[::2], LR[1::2]):
        ans.append(A[r] - A[l - 1])

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [n % 2 and n in primes and (n + 1) // 2 in primes for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, open(0).read().split())
    ans = []
    for l, r in zip(LR[::2], LR[1::2]):
        ans.append(A[r] - A[l - 1])

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [n % 2 and n in primes and (n + 1) // 2 in primes for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, read().split())
    ans = []
    for l, r in zip(LR[::2], LR[1::2]):
        ans.append(A[r] - A[l - 1])

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [n % 2 and n in primes and (n + 1) // 2 in primes for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, read().split())
    ans = [0] * Q
    for i, (l, r) in enumerate(zip(LR[::2], LR[1::2])):
        ans[i] = A[r] - A[l - 1]

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    N = 10 ** 5
    primes = prime_numbers(N)
    a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
    a = tuple(accumulate(a))

    ans = []
    Q, *LR = map(int, open(0).read().split())
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(a[r] - a[l - 1])

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [n % 2 and n in primes and (n + 1) // 2 in primes for n in range(10 ** 5 + 1)]
    B = [0]
    B.extend(accumulate(A))

    Q, *LR = map(int, read().split())
    ans = [0] * Q
    for i, (l, r) in enumerate(zip(LR[::2], LR[1::2])):
        ans[i] = B[r + 1] - B[l]

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


def main():
    primes = set(prime_numbers(10 ** 5))
    A = [n % 2 and n in primes and (n + 1) // 2 in primes for n in range(10 ** 5 + 1)]
    B = [0]
    B.extend(accumulate(A))

    Q, *LR = map(int, read().split())
    ans = [0] * Q
    for i, (l, r) in enumerate(zip(LR[::2], LR[1::2])):
        ans[i] = B[r + 1] - B[l]

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import bisect

q = int(input())
plist = [2]
like2017 = []
n = 3
while n <= 10 ** 5:
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            break
    else:
        plist.append(n)
        if (n + 1) // 2 in plist:
            like2017.append(n)
    n += 2
for _ in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(like2017, r) - bisect.bisect_left(like2017, l))

Solution (Python):
l=[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]
from bisect import bisect_left as bl,bisect_right as br
q=int(input())
for i in range(q):
    le,r=map(int,input().split())
    print(br(l,r)-bl(l,le))