Problem:
 Score : 400 points    Problem Statement We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.  You are given Q queries.  In the i -th query, given two odd numbers l_i and r_i , find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i .      Constraints  1≤Q≤10^5  1≤l_i≤r_i≤10^5  l_i and r_i are odd.  All input values are integers.         Input Input is given from Standard Input in the following format:  Q  l_1  r_1  :  l_Q  r_Q       Output Print Q lines. The i -th line (1≤i≤Q) should contain the response to the i -th query.        Sample Input 1 1
3 7      Sample Output 1 2   3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.  5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.  7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.   Thus, the response to the first query should be 2 .       Sample Input 2 4
13 13
7 11
7 11
2017 2017      Sample Output 2 1
0
0
1  Note that 2017 is also similar to 2017.       Sample Input 3 6
1 53
13 91
37 55
19 51
73 91
13 49      Sample Output 3 4
4
1
1
1
2

Solution (Python):


import sys
input=sys.stdin.readline
n = 10**5

primes = set(range(3, n+1, 2)) 
for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*3, n+1, i*2))
primes.add(2)

Likes = [0] * (n+1)
cnt = 0
for i in range(1,n+1,2):
    Likes[i-1]=Likes[i-2]
    x = (i+1)//2
    if i in primes and (x in primes or x==2):
        Likes[i]=Likes[i-1] + 1
    else:
        Likes[i]=Likes[i-1]

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

if __name__ == '__main__':
    main()

Solution (Python):
n = 10**5
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False
 
for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, n + 1, i):
        is_prime[j] = False
 
num = [0] * (n + 1)
 
cnt = 0
for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if is_prime[(i + 1) // 2]:
            cnt += 1
    num[i] = cnt
 
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
 
for l, r in LR:
    print(num[r] - num[l - 1])

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


def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


prime_list = primes(100000)
familiar = [0]*100001
for p in prime_list:
    if (p+1)//2 in prime_list:
        familiar[p] = 1
s = [0]*100001
for i in range(100000):
    s[i+1] = s[i] + familiar[i+1]


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

Solution (Python):
Q = int(input())
MIN, MAX = 10**18, 0
LR = []
for q in range(Q):
    l, r = map(int, input().split())
    MIN = min(MIN, l)
    MAX = max(MAX, r)
    LR.append((l, r))

from math import sqrt
from itertools import accumulate
lis = [0]*(MAX+1)
search = [2] + [i for i in range(2, MAX+1) if i%2!=0]
lim = sqrt(MAX)
prime = set()
while 1:
    n = search[0]
    if n>=lim:
        break
    prime.add(n)
    if (n+1)//2 in prime:
        lis[n] = 1
    search = [i for i in search if i%n!=0]
for s in search:
    prime.add(s)
    if (s+1)//2 in prime:
        lis[s] = 1
clis = list(accumulate(lis))
for l, r in LR:
    print(clis[r]-clis[l-1])

Solution (Python):
import bisect

n = 10**5
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False

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

num = [0] * (n + 1)

cnt = 0
for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if is_prime[(i + 1) // 2]:
            cnt += 1
    num[i] = cnt

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

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

Solution (Python):
def isPrime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    cur = 3
    while True:
        if cur * cur > x:
            break
        if x % cur == 0:
            return False
        cur += 2
    return True


Q = int(input())
num = [0] * 100010
for i in range(3,100001,2):
    if isPrime(i) and isPrime((i+1)//2):
        num[i] += 1
for i in range(0,100001):
    num[i+1] += num[i]


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

Solution (Python):
from itertools import accumulate
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
prime_set = set(get_sieve_of_eratosthenes(10**5+1))
like_2017_list =  [0 for _ in range(10**5+1)]
like_2017_set = set()
for n in range(1, 10**5, 2):
    if n in prime_set and (n+1)//2 in prime_set:
        like_2017_list[n] = 1
        like_2017_set.add(n)
like_2017_list = list(accumulate(like_2017_list))

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

Solution (Python):
import math
import sys
sys.setrecursionlimit(10000000)
Q = int(input())
l_r = [list(map(int, input().split())) for _ in range(Q)]

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


def like(x):
    if isprime(x) and isprime((x+1)//2):
        return True
    
    return False

x_dict = {1:0}
def count_like(x):
    if x in x_dict:
        return x_dict[x]
    x_dict[x] = count_like(x-1) + like(x)
    return x_dict[x]

for i in range(Q):
    print(count_like(l_r[i][1]) - count_like(l_r[i][0]) + int(like(l_r[i][0])))

Solution (Python):
N = int(input())
MAX=110000
S = [_+2 for _ in range(MAX)]
old = S
i = 0
while True:
  new = set([])
  t = old[i]
  for j in range(len(old)):
    if old[j] == t or old[j]%t != 0:
      new.add(old[j])
  if len(old) == len(new):
    break
  old = list(new)
  old.sort()
  i += 1



A = [0 for _ in range(MAX)]  
for i in range(MAX):
  if i%2 == 0:
    continue
  if i in new and (i+1)//2 in new:
    A[i] = 1
SUM = [0 for _ in range(MAX)] 
for i in range(1,MAX):
  SUM[i] += A[i]+SUM[i-1]


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

Solution (Python):


import sys

import math






















from itertools import accumulate             





def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    class Eratos:
        def __init__(self, num):
            '''
            O(nlglgn) で num までの素数判定テーブルを作る
            >>> e = Eratos(10)
            >>> e.table
            [False, False, True, True, False, True, False, True, False, False, False]
            '''
            assert(num >= 1)
            self.table_max = num
            
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    
                        self.table[j] = False
        
        def is_prime(self, num):
            '''
            O(1) で素数判定を行う
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [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]
            '''
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            '''
            O(√n) で素因数分解を行う
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            '''
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            
            factorized_dict = dict()
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            
            
            for p in candidate_prime_numbers:
                if num == 1:    
                    break
                if num % p == 0:
                    cnt = 0
                    while num % p == 0:
                        num //= p
                        cnt += 1
                    factorized_dict[p] = cnt
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
        
        def enum_divisor(self, num):
            '''
            O(√n) で約数列挙を行う
            >>> e = Eratos(10000)
            >>> e.enum_divisor(4)
            [1, 2, 4]
            >>> e.enum_divisor(19)
            [1, 19]
            >>> e.enum_divisor(100)
            [1, 2, 4, 5, 10, 20, 25, 50, 100]
            '''
            divisor_small = []
            divisor_large = []
            for i in range(1, int(math.sqrt(num)) + 1):
                if num % i == 0:
                    divisor_small.append(i)
                    if i != num // i:
                        divisor_large.append(num // i)
            divisor_large.reverse()
            return divisor_small + divisor_large
    
    e = Eratos(10**5)
    similar_to_2017 = [0] * (10**5+1)
    for num in range(3, 10**5+1, 2):
        if e.is_prime(num) and e.is_prime((num+1)//2):
            similar_to_2017[num] = 1
    accum_similar_to_2017 = list(accumulate(similar_to_2017))
    
    q = ii()
    for _ in range(q):
        l, r = mi()
        print(accum_similar_to_2017[r] - accum_similar_to_2017[l-1])



if __name__ == "__main__":
    main()

Solution (Python):
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False

    return True

like = []
for i in range(1,100000,2):
    if is_prime(i) and is_prime((i+1)//2):
        like.append(i)
like_set  = set(like)
q = int(input())
import bisect
for _ in range(q):
    l,r = map(int,input().split())
    a = bisect.bisect_left(like,l)
    b = bisect.bisect_right(like,r)
    print(b-a)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






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






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primes = []
  while seachList[0] <= max:
    primes.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primes.extend(seachList)
  return primes

P = make_primes(100000)[1:]
like = []
for p in P:
  if len(factorization((p+1)//2)) == 1 and factorization((p+1)//2)[0][1] == 1:
    like.append(p)

imosu = [0 for i in range(101000)]
for i in like:
  imosu[i] += 1
  imosu[i+1] -= 1
  
ans = [0]
for i in imosu:
  ans.append(ans[-1]+i)
  
ruiseki = [0]
for i in ans:
  ruiseki.append(ruiseki[-1]+i)
Q = I()
for _ in range(Q):
  l,r = IL()
  print(ruiseki[r+2]-ruiseki[l+1])

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10


    def sieve_of_eratosthenes(upper_bound):
        upper_bound += 1
        P = [True] * upper_bound
        P[0] = P[1] = False
        for i in range(4,upper_bound,2):
            P[i] = False
        for i in range(3,int(upper_bound**0.5),2):
            if P[i]:
                for j in range(i**2,upper_bound,i):
                    P[j] = False
        return P

















    num_like2017 = [0]*(10**5+1)
    primes = sieve_of_eratosthenes(10**5)
    for i in range(1,10**5+1):
        if primes[i] and primes[(i+1)//2]:
            num_like2017[i] = num_like2017[i-1] + 1
        else:
            num_like2017[i] = num_like2017[i-1]
    out = deque()
    Q = II()
    for i in range(Q):
        l,r = LMIIS()
        out.append(num_like2017[r] - num_like2017[l-1])
    
    for o in out:
        print(o)

    
main()

Solution (Python):
def prime_all(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = is_prime[1] = False
    i = 2
    while i*i <= n:
        if is_prime[i]:
            j = 2*i
            while j <= n:
                is_prime[j] = False
                j += i
        i += 1       
    
    return is_prime
  
q = int(input())

max_N = 10**5

primes = prime_all(max_N)

prime_count = [0]*(max_N+1)

j=0
for i in range(2, max_N+1):
    if primes[i] and primes[(i+1)//2]:
        prime_count[i] = prime_count[i-1] + 1
    else:
        prime_count[i] = prime_count[i-1]
        
for i in range(q):
    l,r = map(int,input().split())
    print(prime_count[r] - prime_count[l-1])

Solution (Python):
import bisect

q = int(input())

def pr(n):
    is_prime = [True]*(n+2)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int((n+1)**0.5)+1):
        for j in range(2,i+1):
            if is_prime[i] == False:
                continue
            for k in range(2*i,n+1,i):
                is_prime[k] = False
                
    return is_prime
    
L = pr(10**5*2+2000)

li = []
for i in range(2,10**5 + 1):
    if L[i] and L[(i+1)//2]:
        li.append(i)

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

Solution (Python):
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


t,_ = sieve(100005)
m = [0]
cnt = 0
for i in range(100005):
    
    if i%2==0 and t[i] and t[(1+i)//2]:
        cnt+=1
    m.append(cnt)


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

Solution (Python):
from math import sqrt

q = int(input())

nums = [i for i in range(2, 10**5+1)]
primes = []
while nums[0] < sqrt(10**5):
    n = nums.pop(0)
    primes.append(n)
    new_nums = []
    for num in nums:
        if num % n != 0:
            new_nums.append(num)
    nums = new_nums
primes.extend(nums)
primes_set = set(primes)


flags = []
for i in range(10**5+1):
    flags.append(int(i in primes_set and (i+1)/2 in primes_set))
cum_flags = [0]*len(flags)
cum_flags[0] = flags[0]
for i in range(1, len(flags)):
    cum_flags[i] = cum_flags[i-1]+flags[i]

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

Solution (Python):
from itertools import accumulate

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

p_list = primes(10 ** 5)
cnt = [0] * (10 ** 5 + 2)
for i in range(1, (10 ** 5 + 1), 2):
    if p_list[i] and p_list[(i + 1) // 2]:
        cnt[i] += 1
cnt_sum = list(accumulate(cnt))

q = int(input())
for _ in range(q):
    li, ri = map(int, input().split())
    print(cnt_sum[ri] - cnt_sum[li - 1])

Solution (Python):
from math import sqrt
M = 10**6
p = [1 for i in range(M+1)]
p[0] = 0
p[1] = 0
for x in range(2, int(sqrt(M))+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0

a = [0 for i in range(M+1)]
for i in range(M):
    if i%2 != 0 and p[i] and p[(i+1)//2]:
        a[i] = 1

ans = [0 for i in range(M)]
for i in range(1, M):
    ans[i] = ans[i-1] + a[i]

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

Solution (Python):
from math import sqrt
M = 10**6
p = [1 for i in range(M+1)]
p[0] = 0
p[1] = 0
for x in range(2, int(sqrt(M))+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0

a = [0 for i in range(M+1)]
for i in range(M):
    if i%2 != 0 and p[i] and p[(i+1)//2]:
        a[i] = 1

ans = [0 for i in range(M)]
for i in range(1, M):
    ans[i] = ans[i-1] + a[i]

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

Solution (Python):
import itertools

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

a = sieve(10**5)
b = [0] * (10**5 + 1)
for i in range(10**5+1):
  if a[i] and a[(i+1)//2]:
    b[i] = 1

b = list(itertools.accumulate(b))
ans = []
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  ans.append(b[r] - b[l-1])

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

Solution (Python):
q = int(input())
l, r = [0]*q, [0]*q
for i in range(q):
    l[i], r[i] = map(int, input().split())

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

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

Solution (Python):
q = int(input())
l, r = [0]*q, [0]*q
for i in range(q):
    l[i], r[i] = map(int, input().split())

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

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

s = [0]*(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):
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 







def primes(n):
    isp = [True for _ in range(n+1)]
    isp[0] = False
    isp[1] = False
    l = ceil(sqrt(n))
    n += 1
    for i in range(2, l):
        if not isp[i]: continue
        for j in range(i*2, n, i): isp[j] = False
    return isp

q = int(input())
maxv = 10**5
isp = primes(maxv)
cnt = [0 for _ in range(maxv + 1)]

for i in range(3, maxv+1):
    if i%2 and isp[i] and isp[(i+1)//2]:
        cnt[i] = 1

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

Solution (Python):
def era(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = num**0.5

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

Q=int(input())
l=[]
r=[]
for _ in range(Q):
    L,R=map(int,input().split())
    l.append(L)
    r.append(R)
N=max(r)
input_list=era(N+1)
Prime=set([i for i, b in enumerate(input_list) if b == True])
cnt=[0,0,0]
for i in range(3,N+1):
    cnt.append(cnt[-1])
    if i%2==1 and i in Prime and (i+1)//2 in Prime:
        cnt[i]+=1


for j in range(Q):
    print(cnt[r[j]]-cnt[l[j]-1])

Solution (Python):
from bisect import bisect_left, bisect_right
q = int(input())
lr = []
for _ in range(q):
    l, r = map(int, input().split())
    lr.append((l, r))
primes = set(range(3, 10**5, 2))
primes.add(2)
for i in range(3, 10**5, 2):
    if i not in primes:
        continue
    for j in range(i*2, 10**5, i):
        primes.discard(j)
nums = []
for i in primes:
    if (i+1)//2 in primes:
        nums.append(i)
nums.sort()
for l, r in lr:
    print(bisect_right(nums, r)-bisect_left(nums, l))

Solution (Python):
def main():
    q = int(input())
    
    ma = 10**5+1
    prime = [1]*ma 
    prime[0],prime[1] = 0,0
    for i in range(2,ma):
        if prime[i] == 0:
            continue
        for j in range(i*2,ma,i):
            prime[j] = 0

    
    like = [0]*ma 
    for i in range(ma):
        if i%2 == 0: 
            continue
        if prime[i] == 1 and prime[(i+1)//2] == 1:
            like[i] = 1

    
    rui = [0]*(ma+1)
    for i in range(ma):
        rui[i+1] = rui[i]+like[i]

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

if __name__ == '__main__':
    main()

Solution (Python):
Q = int(input())
maxn = 10**5
is_prime = [True if i%2 == 1 else False for i in range(0, maxn+1) ]
is_prime[0] = False
is_prime[1] = False
is_prime[2] = True
for i in range(3, int(maxn**0.5) + 1, 2):
    if not is_prime[i]:
        continue
    for j in range(i*2, maxn+1, i):
        is_prime[j] = False

ps = [i for i in range(maxn+1) if is_prime[i]]
ps = set(ps)

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

from itertools import accumulate
cs = list(accumulate(c))

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

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

ps = []
maxfac = math.sqrt(10**5)
nums = [i+1 for i in range(1, 10**5)]
while True:
    p = nums[0]
    if maxfac <= p:
        break
    ps.append(p) 
    nums = [num for num in nums if num % p != 0]

ps = set(ps + nums)

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

from itertools import accumulate
cs = list(accumulate(c))

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

Solution (Python):
M = 10**6
p = [1]*M
p[0] = p[1] = 0
for i in range(2, 4*10**4):
    if p[i]:
        for j in range(i*i, M, i):
            p[j] = 0
C = [0]*M
for i in range(2, M):
    if p[i] and p[(i+1)//2]:
        C[i] = C[i-1] + 1
    else:
        C[i] = C[i-1]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(C[r] - C[l-1])

Solution (Python):

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

N = int(1e+5)
max_num = int(N**0.5)
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2,max_num+1):
    if not is_prime[i]:
        continue
    for j in range(i*2,N+1,i):
        is_prime[j] = False

ans = [False] * (N+1)
for i in range(3,N+1,2):
    b = (i+1)//2
    if is_prime[i] and is_prime[b]:
        ans[i] = True

comurative_ans = [0] * (N+1)
sum_true = 0
for i in range(N+1):
    if ans[i] :
        sum_true += 1
    comurative_ans[i] = sum_true
for l,r in query:
    print(comurative_ans[r+1]-comurative_ans[l-1])