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



Sample input:
1
3 7


Sample output:
2

Submission status: Runtime Error

Solution code:
import math
Q=int(input())
N=10**4+1

L = []
R = []
for i in range(Q):
    ll,rr=[int(i) for i in input().split()]
    L.append(ll)
    R.append(rr)

primeN = [2]
for i in range(2, N):
    for j in range(len(primeN)):
        if i % primeN[j] == 0:
            break
        else:
            if j == len(primeN) - 1:
                primeN.append(i)
nita = [0]*N
for i in range(N):
    if i in primeN and (i+1)//2 in primeN:
        nita[i] = nita[i-1] + 1
    else:
        nita[i] = nita[i-1]

for i in range(Q):
    a = nita[R[i]] - nita[L[i]-1]
    print(a)

Submission status: Runtime Error

Solution code:
q = input()


que = []
for i in range(q):
    r = input()
    que.append(r)

def prime(n):
    half = n+1 / 2
    for i in range(n):
        if n % i == 0:
            return(False)
    return(True)



for i in range(len(que)):
    count = 0
    a = int(que[i].split(" ")[0])
    b = int(que[i].split(" ")[1])
    c = min(a, b)
    for i in range(abs(a-b)+1):
        if prime(c + i):
            if prime((c + i + 1)/2):
                count += 1
    print(count)

Submission status: Runtime Error

Solution code:
q = input()


que = []
for i in range(q):
    que.append(q)

def prime(n):
    half = n+1 / 2
    for i in range(n):
        if n % i == 0:
            return(False)
    return(True)



for i in range(len(que)):
    count = 0
    a = int(que[i].split(" ")[0])
    b = int(que[i].split(" ")[1])
    c = min(a, b)
    for i in range(abs(a-b)+1):
        if prime(c + i):
            if prime((c + i + 1)/2):
                count += 1
    print(count)

Submission status: Runtime Error

Solution code:
import sys

Q = int(sys.stdin.readline().strip())
LR = []
for i in range(Q):
    LR.append([int(x) for x in sys.stdin.readline().strip().split()])

N = 10**5
Primes = list(range(N+1))
Primes[1] = 0

for p in Primes:
    if p * p > N+1: break
    if p == 0: continue
    for i in range(p + p, N+1, p):
        Primes[i] = 0

primes = [p for p in Primes if p > 0]

likes = []
r = 0
for n in range(N):
    if n%2 == 1 and Primes[n] > 0 and Primes[n//2+1] > 0:
        r += 1
    likes.append(r)

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

Submission status: Runtime Error

Solution code:
p = [True] * 100000
for x in xrange(2, int(100000 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100000):
            if y * x >= 100000:
                break
            p[x * y] = False
p[0], p[1] = False, False
e, s = [], 0
for i in xrange(100000):
    e.append(s)
    if p[i] and p[(i + 1) / 2]:
        s += 1
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print e[r + 1] - e[l]

Submission status: Runtime Error

Solution code:

def isprime(x):
  if x < 2: return False
  for d in range(2, int(x**0.5)+1):
    if x % d == p: return False
  return True

isp = list(map(isprime, range(100001)))
w = [0]*100001
for i in range(100001):
  if i > 2 and isp[i] and isp[(i + 1)//2]:
    w[i] = 1

for i in range(1,100001):
  w[i] += w[i-1]

Q = int(input())
for i in range(Q):
  L,R = map(int, input().split())
  print(w[R] - w[L-1])

Submission status: Runtime Error

Solution code:
from itertools import accumulate
# Eratosthenes
def eratosthenes(n):
    prime_table = [False,False,True]+[False if i%2!=0 else True for i in range(n-2)]
    i=3
    while i*i<=n:
        if prime_table[i]:
            j=i*i
            while j<=n:
                prime_table[j]=False
                j+=i
        i+=2
    return prime_table

pt=eratosthenes(10001)
ok=[0 for i in range(10001)]
i=1
while i<10001:
    if pt[i] and pt[(i+1)//2]:
        ok[i]=1
    i+=2
ok=list(accumulate(ok))

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