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())

n = 10**5

import math
def primes():
    sieve = [True] * (n + 1)
    for x in range(2, math.ceil(math.sqrt(n))):
        y = x * 2
        while y <= n:
            sieve[y] = False
            y += x
    return [i for (i, x) in enumerate(sieve[2:], 2) if x]

list_p = primes()
set_p = set(list_p)

tbl = [0] * (n + 1)
for p in list_p:
    tbl[p] = 1 if ((p + 1) // 2) in set_p else 0

import itertools
tbl = list(itertools.accumulate(tbl))

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

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

primeList = [1] * (100001)
cumA = [0] * (100001)

primeList[0] = 0
primeList[1] = 0

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


for i in range(1,100000):
  cumA[i+1] = cumA[i]
  if i%2 == 0 and primeList[(i+2)//2] == 1:
    cumA[i+1] += primeList[i+1]

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