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: Accepted

Solution code:
from functools import reduce
import math
import collections
## エラトステネスの篩
def eratosthenes(num):
    is_prime = [1]*num
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2,num):
        if is_prime[i] == 1:
            for j in range(i*i,num,i):
                is_prime[j] = 0
    return is_prime
            
def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        s1, s2 = (int(_) for _ in input().split())
        l.append(s1)
        r.append(s2)
    cnt = 1
    is_prime = eratosthenes(100005)

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

    for i in range(1,100004):
        c[i+1] += c[i]
    ans = []    
    for i in range(Q):
        ans.append(c[r[i]]-c[l[i]-1])
            
    print('\n'.join(str(_) for _ in ans))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []

    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1

    return prime_list


def solve(Q: int, l: "List[int]", r: "List[int]"):

    # primes = eratosthenes_sieve(10**5)
    # prime_kai = [p for p in primes if (p+1)//2 in primes]

    prime_kai = [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]
    N = len(prime_kai)

    # print(prime_kai[:10])
    for ll, rr in zip(l, r):
        # print("({}, {})".format(ll, rr))
        left = -1
        right = N
        while right - left > 1:
            mid = left + (right - left) // 2
            if prime_kai[mid] < ll:
                left = mid
            else:
                right = mid
        hidari = right

        left = -1
        right = N
        while right - left > 1:
            mid = left + (right - left) // 2
            if prime_kai[mid] < rr+1:
                left = mid
            else:
                right = mid
        migi = right
        # print(hidari, migi)
        print(migi - hidari)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    Q = int(next(tokens))  # type: int
    l = [int()] * (Q)  # type: "List[int]"
    r = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(Q, l, r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def prime(n):
  if n==1:
    return False
  elif n==2 or n==3:
    return True
  else:
    for i in range(2,int(n**0.5)+1):
      if n%i==0:
        return False
    else:
      return True

ans=[0]*(10**5+1)
for i in range(3,10**5+1,2):
  if prime(i) and prime((i+1)//2):
    ans[i]=1
for i in range(1,10**5+1):
  ans[i]=ans[i]+ans[i-1]
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(ans[r]-ans[l-1])

Submission status: Accepted

Solution code:
import math
import bisect

def is_prime(n):
    #if n % 2 == 0 and n > 2: 
    #    return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))


N = int(input())

P = [3]

for i in range(5,10**5,4) :
    if (is_prime(i)) and (is_prime((i+1)//2)) :
        P.append(i)

ans = []

for i in range(N) :
    l,r = map(int,input().split())    
    ans.append(bisect.bisect_right(P,r) - bisect.bisect_left(P,l))

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

Submission status: Accepted

Solution code:
p_list=[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]

p_flg_=[0 for i in range(100001)]

for p in p_list:
    p_flg_[p]=1

s=0
S = [0]

for i in range(1,100001):
    s+=p_flg_[i]
    S.append(s)

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

Submission status: Accepted

Solution code:
M = 10**5+1
p = [1]*M
p[0] = p[1] = 0
for i in range(2, 10**3):
    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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
import math
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
primes = primes(10**5)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in primes:
        if (i+1)//2 in primes:
            cnt += 1
    dp[i] = cnt
 
    
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[r]-dp[l-2])

Submission status: Accepted

Solution code:
import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
primes = primes(10**5)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in primes:
        if (i+1)//2 in primes:
            cnt += 1
    dp[i] = cnt

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

Submission status: Accepted

Solution code:
a = set([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])
Q = int(input())

li = [0]*1000000
for i in range(100000):
  li[i+1] = li[i] + (1 if i+1 in a else 0)

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

Submission status: Accepted

Solution code:
N = 10**5
p = [0]*(N+1)
p[2] = 1
primes = [2]

for i in range(3,N+1):
  f = 1
  for t in primes:
    if t*t > i:
      break
    if i%t == 0:
      f = 0
      break
  if f == 1:
    primes.append(i)
    p[i] = 1
    if p[(i+1)//2] >= 1:
      p[i] = 2

m = 0
s = [0]*(N+1)
for i in range(1,N+1):
  m += (p[i]==2)
  s[i] = m
  
for i in range(int(input())):
  l,r = map(int,input().split())
  print(s[r]-s[l-1])

Submission status: Accepted

Solution code:
N = 10**5
p = [0]*(N+1)
q = [0]*(N+1)

p[2] = 1
primes = [2]

for i in range(3,N+1):
  f = 1
  for t in primes:
    if t*t > i:
      break
    if i%t == 0:
      f = 0
      break
  if f == 1:
    primes.append(i)
    p[i] = 1
    if p[(i+1)//2]:
      q[i] = 1
m = 0
s = [0]*(N+1)
for i in range(1,N+1):
  m += q[i]
  s[i] = m
  
for i in range(int(input())):
  l,r = map(int,input().split())
  print(s[r]-s[l-1])

Submission status: Accepted

Solution code:
import numpy as np
N_MAX = 10**5

def make_prime_table(n):
    table = np.ones(n+1, dtype=np.int)
    table[0] = 0
    table[1] = 0
    for i in range(2,int(n**0.5)+1):
        if (1 == table[i]):
            j = i*2
            while j<=n:
                table[j] = 0
                j += i
    return table
  
prime_table = make_prime_table(N_MAX)
like2017_table = np.zeros(N_MAX+1, dtype=np.int)

c = 0
for i in range(3,N_MAX,2):
  if (prime_table[i] == 1):
    if (prime_table[(i+1)//2] == 1):
      c += 1
  like2017_table[i] = c
  like2017_table[i+1] = c

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

Submission status: Accepted

Solution code:
q=int(input())
P2017=[]
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 [i for i in range(n + 1) if is_prime[i]]
P=primes(10**5)
for p in P:
  if (p+1)//2 in P:
    P2017.append(p)
LR=[0]*(10**5)
for p in P2017:
  LR[p]+=1
for i in range(10**5-1):
  LR[i+1]+=LR[i]
for i in range(q):
  l,r=map(int,input().split())
  print(LR[r]-LR[l-1])

Submission status: Accepted

Solution code:
#coding:utf-8
def isPrime(x):
    if x==1:return False
    if x==2 or x==3:return True
    if x%2==0:return False
    i=3
    while i*i<=x:
        if x%i==0:return False
        i+=2
    return True
pr=[None]*(10**5+1)
for i in range(10**5+1):
    pr[i]=isPrime(i)

#ary[l]:=#(1~l)
ary=[None]*(10**5+1)
ary[0]=0
ary[1]=0
ary[2]=0
for x in range(3,10**5+1):
    if pr[x] and pr[(x+1)/2]:
        ary[x]=ary[x-2]+1
    else:
        ary[x]=ary[x-2]
Q=input()
for i in range(Q):
    l,r=map(int,raw_input().split())
    if l!=1:
        print(ary[r]-ary[l-2])
    else:
        print(ary[r])

Submission status: Accepted

Solution code:
Q=int(input())
lr=[list(map(int,input().split())) for i in range(Q)]
def is_prime(N):
    is_prime=[True]*(N+1)
    is_prime[0:2]=False,False
    for i in range(int(N**0.5)+1):
        if is_prime[i]==False:
            continue
        for j in range(i*2,N+1,i):
            is_prime[j]=False
    return is_prime

prime=is_prime(10**5)
like=[0]*(10**5+1)
for i in range(1,10**5+1):
    if i%2==1 and prime[i] and prime[(i+1)//2]:
        like[i]=like[i-1]+1
    else:
        like[i]=like[i-1]
for l,r in lr:
    print(like[r]-like[l-1])

Submission status: Accepted

Solution code:
import bisect
p=[]
for i in range(3,10**5+1,2):
    for j in range(3,int(i**0.5)+1,2):
        if i%j==0:
            break
    else:p.append(i)
n=[3]
for i in p:
    x=(i+1)//2
    y=bisect.bisect_left(p,x)
    if x==p[y]:n.append(i)
for _ in range(int(input())):
    l,r=map(int,input().split())
    print(bisect.bisect_right(n,r)-bisect.bisect_right(n,l-1))

Submission status: Accepted

Solution code:
import math

# Sieve of Eratosthenes
is_prime = [1] * (10 ** 5)
is_prime[0:2] = 0, 0
for i in range(2, int(math.sqrt(len(is_prime)))):
    if is_prime[i]:
        for j in range(i * 2, len(is_prime), i):
            is_prime[j] = 0

# Similar to 2017
a = [0] * (10 ** 5)
for i in range(1, len(a), 2):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        a[i] = 1

# Cumulative sum
s = [0] * (10 ** 5 + 1)
for i in range(len(a)):
    s[i + 1] = s[i] + a[i]

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

Submission status: Accepted

Solution code:
Q=int(input())
M=10**5
from collections import defaultdict,deque
prime=defaultdict(int)
prime[2]=1
cnt=defaultdict(int)
def check(N):
    for k in range(2,int(N**0.5)+2):
        if N%k==0:
            return False
    return True
    
for N in range(2,10**5):
    cnt[N]+=cnt[N-1]
    if N%2==1:
        if check(N):
            prime[N]=1
            if prime[(N+1)//2]==1:
                cnt[N]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
import itertools
import math
import operator
import sys


def get_primes(max=None, count=None):
    """
    素数列挙
    昇順にソートされています
    https://qiita.com/Ishotihadus/items/73e107271275611f05f2
    :param int max:
    :param int count:
    :return:
    """
    assert max or count
    if count:
        raise NotImplementedError()
    if max <= 1:
        return []

    primes = [2]
    sieve = [False for _ in range(max + 1)]
    p = 3
    while p <= max:
        primes.append(p)
        sieve[p] = True
        if p <= math.sqrt(max):
            for i in range(p * (p | 1), max + 1, p * 2):
                sieve[i] = True
        while p <= max and sieve[p]:
            p += 2

    return primes


sys.setrecursionlimit(10000)
INF = float('inf')

PRIMES = set(get_primes(max=10 ** 5))


def is_similar_2017(n):
    return n in PRIMES and (n + 1) // 2 in PRIMES


similar_counts = list(itertools.accumulate(
    [1 if is_similar_2017(n) else 0 for n in range(10 ** 5)],
    operator.add
))

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

Submission status: Accepted

Solution code:
import bisect

def PRIME(N):
    LIM = int(N**0.5)+2
    for i in range(2, LIM):
        if N%i == 0:
            return False
    return True

q = int(input())
prime, ans = {2:True}, []
for i in range(3, 100001):
    if i%2 == 0:
        prime[i] = False
        continue
    a = PRIME(i)
    prime[i] = a
    if a:
        if prime[(i+1)//2]:
            ans.append(i)

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

Submission status: Accepted

Solution code:
import math


def primes(x):
    x+=1
    if x < 2:
        return []

    prime = [i for i in range(x)]
    prime[1] = 0

    for p in prime:
        if p > math.sqrt(x):
            break
        if p == 0:
            continue
        for non_prime in range(2 * p, x, p):
            prime[non_prime] = 0

    return [p for p in prime if p != 0]


n = int(input())
l = [list(map(int, input().split())) for i in range(n)]

p = primes(10**5)

q = []
s = 0
for i in range(len(p)):
    for j in range(s,len(p)):
        if (p[i]+1)//2 == p[j]:
            q.append(p[i])
            s = j
            break
        elif (p[i]+1)//2 < p[j]:
            s = j
            break


for i in range(n):
    ans = 0
    for j in range(len(q)):
        if l[i][0]<=q[j]<=l[i][1]:
            ans +=1
    print(ans)