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
num = 100000
s = set([i for i in range(2,num+1)])
p = set()
mi = 0
while mi<=math.sqrt(num):
    mi = min(s)
    t = set([i*mi for i in range(1,num//mi+1)])
    p.add(mi)
    s-=t
p = p|s
p2 = set([i for i in p if (i+1)//2 in p])

q = int(input())
for i in range(q):
    l , r = map(int, input().split())
    s2 = set([i for i in range(l,r+1)if in p2])
    print(len(s2))

Submission status: Runtime Error

Solution code:
import bisect
N = 10**6
dp = [1] * (N+1)
dp[0] =  dp[1] =  0
prime = []
for i in range(2,N+1):
    if dp[i]:
        for j in range(i*i, N+1, i):
            dp[j] = 0
like2017 = [0] * (N+1)
for n in range(N+1):
    if dp[n]==0:
        continue
    query = (p+1)//2
    if dp[query]==1:
        like2017[n] = 1


for n in range(N):
    line2017[n+1] += like2017[n]
    
Q = int(input())
for q in range(Q):
    l, r = map(int,input().split())
    print (like2017[r]-like2017[l])

Submission status: Runtime Error

Solution code:
from sys import stdin
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

prime_list=[i for i in range(1,10001) if is_prime(i)]
oppai=[0]*10005
for i in range(2, 10001):
    if i in prime_list and (i+1)//2 in prime_list:
        oppai[i-1]=oppai[i-2]+1
    else:oppai[i-1]=oppai[i-2]
#print(oppai)
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=map(int,(input().split()))
    if a==b:
        bb = oppai[b - 1]
        aa = oppai[a - 2]
        count = bb - aa
        print(count)
    else:
        if a>=2:
            bb=oppai[b-1]
            aa=oppai[a-2]
            count = bb - aa
            print(count)
        else:
            bb = oppai[b - 1]
            count = bb
            print(count)

Submission status: Runtime Error

Solution code:
from sys import stdin
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

prime_list=[i for i in range(1,10001) if is_prime(i)]
oppai=[0]*10005
for i in range(3, 10001):
    if i in prime_list and (i+1)//2 in prime_list:
        oppai[i-1]=oppai[i-2]+1
    else:oppai[i-1]=oppai[i-2]
#print(oppai)
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=map(int,(input().split()))
    if a==b:
        if a in  prime_list and ((a+1)//2) in  prime_list:
            count+=1
            print(count)
    else:
        if a>=2:
            bb=oppai[b-1]
            aa=oppai[a-2]
            count = bb - aa
            print(count)
        else:
            bb = oppai[b - 1]
            count = bb
            print(count)

Submission status: Runtime Error

Solution code:
from sys import stdin
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

prime_list=[i for i in range(1,10001) if is_prime(i)]
oppai=[0]*10000
for i in range(3, 10001):
    if i in prime_list and (i+1)/2 in prime_list:
        oppai[i-1]=oppai[i-2]+1
    else:oppai[i-1]=oppai[i-2]
#print(oppai)
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=map(int,(input().split()))
    if a==b:
        if a in  prime_list and ((a+1)/2) in  prime_list:
            count+=1
    else:
        if a>=2:
            bb=oppai[b-1]
            aa=oppai[a-2]
            count = bb - aa
        else:
            bb = oppai[b - 1]
            count = bb

    print(count)

Submission status: Runtime Error

Solution code:
from sys import stdin
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

prime_list=[i for i in range(1,10001) if is_prime(i)]
oppai=[0]*10000
for i in range(3, 10000):
    if i in prime_list and (i+1)/2 in prime_list:
        oppai[i-1]=oppai[i-2]+1
    else:oppai[i-1]=oppai[i-2]
#print(oppai)
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=map(int,(input().split()))
    if a==b:
        if a in  prime_list and ((a+1)/2) in  prime_list:
            count+=1
    else:
        if a>=2:
            bb=oppai[b-1]
            aa=oppai[a-2]
            count = bb - aa
        else:
            bb = oppai[b - 1]
            count = bb

    print(count)

Submission status: Runtime Error

Solution code:
from sys import stdin
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

prime_list=[i for i in range(1,10001) if is_prime(i)]
oppai=[0]*10000
for i in range(3, 10000):
    if i in prime_list and (i+1)/2 in prime_list:
        oppai[i-1]=oppai[i-2]+1
    else:oppai[i-1]=oppai[i-2]
#print(oppai)
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=map(int,(input().split()))
    if a==b:
        if a in  prime_list and ((a+1)/2) in  prime_list:
            count+=1
    else:
        bb=oppai[b-1]
        aa=oppai[a-2]
        count=bb-aa
    print(count)

Submission status: Runtime Error

Solution code:
import math
Q = int(input())#numの数の個数
Query = []
maxn=0
for _ in range(Q):
    l,r = map(int,input().split())
    Query.append((l,r))
    maxn = max(maxn,r)
N = maxn
num = [0]*(N+2)#部分和を計算したい数列
def souwa(left,right,ruisekiwa):#0based,numの[left,right)間の総和を計算
   return ruisekiwa[right]-ruisekiwa[left]
def using_sqrt(N):#入力 対象の整数,出力,素数ならば1,合成数ならば1
    flag = 0
    for i in range(2,math.floor(math.sqrt(N))+1):
        if N % i == 0:
            flag = 1
            break
        else:
            continue
    if flag == 1:
        return 0
    else:
        return 1

for i in range(1,N+2,2):
    if using_sqrt(i)==1 and using_sqrt((i+1)//2)==1:
        num[i] = 1
ruisekiwa = [0]*(N+2)
ruisekiwa[0] = 0
num[1] =0
for i in range(1,N+2):#累積和の前処理
    ruisekiwa[i]=num[i-1]+ruisekiwa[i-1]

for q in Query:
    print(souwa(q[0],q[1]+1,ruisekiwa)

Submission status: Runtime Error

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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 input():
    return sys.stdin.readline().rstrip()


def main():
    # [0 is True?, 1 is True?, ..., 10000 is True?]
    table = [False for _ in range(10001)]
    for i in range(1, 10001, 2):
        table[i] = is_prime(i) and is_prime((i + 1) // 2)

    cumsum = [0 for _ in range(10001)]
    for i in range(1, 10001):
        cumsum[i] = cumsum[i - 1]
        if table[i]:
            cumsum[i] += 1

    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        res = cumsum[r] - cumsum[l]
        if table[l]:
            res += 1
        print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
q=int(input())
pn=[2]
qn=[0]*10**5+1
c=0
for i in range(1, 10**5+1,2):
    for i2 in pn:
        if i % i2 == 0:
            break
        else:
            pn.append(i)
for i in range(10**5+1):
    if (pn[i]+1)/2 in pn:
        c+=1
    qn[i]=c
for _ in range(q):
    l,r = map(int, input().split())
    print(qn[r]-qn[l-1])

Submission status: Runtime Error

Solution code:
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
pn=[2]
for L in range(3, 10**5, 2):
    for L2 in pn:
        if L % L2 == 0:
            break
    else:
        if (L+1)/2 in pn:
            pn.append(L)
pn.pop(0)
for i in range(q):
    print(len([i for i in pn if lr[i][0]<=i<=lr[i][1]]))

Submission status: Runtime Error

Solution code:
import math
from itertools import accumulate

Q = int(input())
LR = []

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    # print(int(math.sqrt(n)))
    for i in range(2,int(math.sqrt(n))+1):
        for j in range(i*2, n+1 ,i):
            is_prime[j] = False

    return is_prime

def like2017(is_prime,n):
    solve = [0] * (n+1)
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[int((i+1)/2)]:
            solve[i] = 1
        
    return solve

for _ in range(Q):
    t = [int(i) for i in input().split(' ')]
    LR.append(t)

L = 100
is_prime = primes(L)
solve = like2017(is_prime,L)
# print(solve)
ans = list(accumulate(solve))
# print(ans)

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

Submission status: Runtime Error

Solution code:
import fractions

Q = int(input())
LR = []

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    # print(int(math.sqrt(n)))
    for i in range(2,int(fractions.sqrt(n))+1):
        for j in range(i*2, n+1 ,i):
            is_prime[j] = False

    return is_prime

def like2017(is_prime,n):
    solve = [False] * (n+1)
    for i in range(3,n+1,2):
        if i < n and i >2:
            solve[i] = is_prime[i] and is_prime[int((i+1)/2)]

    return solve

for _ in range(Q):
    t = [int(i) for i in input().split(' ')]
    LR.append(t)

L = 10**5 
is_prime = primes(L)
solve = like2017(is_prime,L)
for l, r in LR:
    # print(solve[l:r+1])
    print(solve[l:r+1].count(True))

Submission status: Runtime Error

Solution code:
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

MAGIC_NUMBER = 100000
isprime = [True] * (MAGIC_NUMBER + 1)
for p in range(2, MAGIC_NUMBER + 1):
    if not isprime[p]: continue
    i_p = 2
    while p * i_p <= MAGIC_NUMBER:
        isprime[p * i_p] = False
        i_p += 1

primes = []
for p in range(2, MAGIC_NUMBER + 1):
    if isprime[p]: primes.append(p)

candidates = []
for p in primes:
    if p % 2 == 0: continue
    #
    if isprime[(p + 1) // 2]: candidates.append(p)


import bisect
    
for i, (li, ri) in enumerate(lr):
    i_l = bisect.bisect_left(candidates, li)
    i_r = bisect.bisect_left(candidates, ri)
    #
    if candidates[i_r] == ri: i_r += 1
    print(i_r - i_l)