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 bisect import bisect_left,bisect_right
pn = [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())
lr=[[int(i) for i in input().split()] for _ in range(Q)]
for l,r in lr:
    print(bisect_right(pn, r)-bisect_left(pn,l))

Submission status: Accepted

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

max_val = max([lr[1] for lr in lr_list])

# エラトステネスの篩
num_list = list(range(max_val + 1))
for num in num_list[2:max_val // 2 + 1]:
    if num > 0:
        for i in range(num*2, max_val+1, num):
            num_list[i] = -1

prime_num_set = set([num for num in num_list if num>0][1:])

# 累積和
sum_list = [0, 0, 0]
for i in range(3, max_val+1):
    if i in prime_num_set and (i+1)//2 in prime_num_set:
        sum_list.append(sum_list[-1]+1)
    else:
        sum_list.append(sum_list[-1])

for l, r in lr_list:
    print(sum_list[r] - sum_list[l-1])

Submission status: Accepted

Solution code:
def main():
    q=int(input())
    aa=0
    bb=0
    a=[]
    b=[]
    ac=[]
    bc=[]
    for _ in range(q):
        aa,bb=map(int,input().split())
        a.append(aa)
        b.append(bb)
        # ac.append(aa)
        # bc.append(bb)

    # sorted(a)
    # sorted(b)
    bm=max(b)
    ans=[0]*100001
    flg=[0]*100001
    flg[0]=1
    flg[1]=1
    ans[2]=1
    ii=int((bm+1)**0.5)
    for i in range(2,100001):

        if flg[i]==0:
            flg[i]=1
            ans[i]=1
            for j in range(i,100001,i):
                flg[j]=1
    ans2=[]
    cnt=0
    for i in range(0,100001):
        if ans[i]==1 and ans[(i+1)//2]==1:
            cnt+=1
        ans2.append(cnt)
    # print(ans[:11])
    # print(ans2[:11])
    for i in range(0,q):
        print(ans2[b[i]]-ans2[a[i]-1])
    # print(ans[:8])
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# D - 2017-like Number

# # n以下の全ての素数のセットを返す関数
# def prime_set(n):
#     primes = set(range(2, n+1))
#     for i in range(2, int(n**0.5) + 1):
#         primes.difference_update(range(i*2, n+1, i))
#     return primes

# p_set = prime_set(10**5)
# like_number = []

# for i in range(1, 10**5, 2):
#     if i in p_set and (i+1)//2 in p_set:
#         like_number.append(i)

like_number = [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]

import sys, bisect

Q = int(sys.stdin.buffer.readline())
for _ in range(Q):
    l, r = map(int, sys.stdin.buffer.readline().split())
    print(bisect.bisect_right(like_number, r) - bisect.bisect_left(like_number, l))

Submission status: Accepted

Solution code:
n=100001
a=[True]*n
b=[0]*n
a[0]=False
a[1]=False
for i in range(2,n):
    if a[i]:
        for j in range(i*2,n,i):
            a[j]=False

cnt=0
for i in range(3,n):
    if a[i] and a[(i+1)//2]:
        cnt+=1
    b[i]=cnt
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(b[r]-b[l-1])

Submission status: Accepted

Solution code:
import math

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

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 = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
sosu_list = get_sieve_of_eratosthenes(10**5)
sosu = [0]*10**5
for i in sosu_list:
  sosu[i] = 1
acc = [0]*10**5
for i in range(3, 10**5, 2):
  if sosu[i] and sosu[(i+1)//2]:
    acc[i] = acc[i-2] + 1
  else:
    acc[i] = acc[i-2]

for l, r in lr:
  if l == 1:
    print(acc[r])
  else:
  	print(acc[r]-acc[l-2])

Submission status: Accepted

Solution code:
from math import sqrt
M = 10**5+10
p = [1]*(M+1)
p[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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

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 table

def solve(Q: int, l: "List[int]", r: "List[int]"):
    primes = sieve(10**5)
    hash_table = {}

    for prime in primes:
        hash_table[prime] = True
    
    like_number_list = []
    for prime in primes:
        if hash_table.get((prime+1)/2) == True:
            like_number_list.append(prime)
    
    ## i以下の最大の2017likenumberの個数
    ruiseki_like_number = [0]*(10**5+1)
    for like in like_number_list:
        ruiseki_like_number[like] += 1

    from itertools import accumulate
    ruiseki_like_number = list(accumulate(ruiseki_like_number))

    for i in range(Q):
        left = ruiseki_like_number[l[i]-1]
        right = ruiseki_like_number[r[i]]
        print(right-left)
    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:
import bisect as bi

def ispr(n):
    if n==1:
        return False
    elif n==2:
        return True
    elif n%2==0:
        return False
    else:
        k=3
        while k**2<=n:
            if n%k==0:
                return False
            else:
                k+=2
        return True

def is2007like(n):
    return ispr(n) and ispr((n+1)//2)

p=[n for n in range(3,10**5+1,2) if is2007like(n)]

for i in range(int(input())):
    l,r=map(int,input().split())
    jl=bi.bisect(p,l-1)
    jr=bi.bisect(p,r+1)-1
    print(jr-jl+1)

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import bisect
import sys
input = sys.stdin.readline

Q=one_int()

import math
lim = int(math.pow(10, 5))
is_prime = [True for _ in range(lim+1)]
is_prime[0], is_prime[1] = False, False
for i in range(2, int(math.sqrt(lim))+1):
    if is_prime[i]:
        for j in range(i*2, lim+1, i):
            is_prime[j] = False
 

# sosu_dict = {s:0 for s in sosuu_list}

like_list = [0 for i in range(10**5 + 1)]
count=0
for i in range(10**5):
    if (is_prime[(i+1)//2]) and (is_prime[i]):
        count+=1
    like_list[i] = count

for i in range(Q):
    l,r = many_int()
    print(like_list[r]-like_list[l-1])

Submission status: Accepted

Solution code:
primes = [2]
for c in range(3,10**5+1,2):
    isPrime = True
    for p in primes:
        if p*p>c: break
        if c%p==0:
            isPrime=False
            break
    if isPrime: primes.append(c)

primeset = set(primes)

like2017s = set([p for p in primes if (p+1)//2 in primeset])

k = [0]*(10**5+10)
for x in range(1, 10**5+10):
    if x in like2017s:
        k[x]=k[x-1]+1
    else:
        k[x]=k[x-1]
	
Q = int(input())
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print(k[r]-k[l-1])

Submission status: Accepted

Solution code:
import bisect

def prime_sieve(end):
    assert end > 1
    is_prime = [True for i in range(end)]
    is_prime[0], is_prime[1] = False, False
    primes = list()
    for i in range(2,end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes 

q = int(input())
lr = [list(map(int, input().split())) for i in range(q)]
a = prime_sieve(100001)
b = set(a)
c = []
for i in a:
  if (i+1) // 2 in b:
    c.append(i)
for l,r in lr:
  ans = bisect.bisect_right(c,r) - bisect.bisect_left(c,l)
  print(ans)

Submission status: Accepted

Solution code:
Q = int(input())
ans = 0
INF = 10 ** 5
is_prime = [1] * INF
rui = [0] * (INF + 1)
def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

eratorasu()
sosu = [0] * INF
for i in range(INF):
    if is_prime[i] == 1 and is_prime[(i + 1) // 2] == 1:
        sosu[i] = 1

rui = [0] * (INF + 1)
for i in range(INF):
    rui[i + 1] = rui[i] + sosu[i]

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

Submission status: Accepted

Solution code:
# ほんとうに全ての値を最初に計算し、累積和のリストを作成してしまおう。
# 計算時間は421msでOKだけど、答えが間違っている。＝＞なおした

import math

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


# 2017に似た数

def is_like2017(n):
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False


Q = int(input())

l_list = [0]*Q
r_list = [0]*Q

for i in range(Q):
    l_list[i], r_list[i] = map(int, input().split())
    

ans = [0]

for i in range(1, 100000+1):
    if i % 2 == 0:
        ans.append(ans[i-1])
    elif is_like2017(i):
        ans.append(ans[i-1] + 1)
    else:
        ans.append(ans[i-1])    
        
for i in range(Q):
    print(ans[r_list[i]]-ans[l_list[i]-1])

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = 10**5 + 2
    E = [False]*2 + [True]*N
    for i in range(2,int(sqrt(N)+1)):
        if E[i]:
            j = 2*i            
            while j < N:
                E[j]=False
                j+=i
    memo = [0]*N
    for i in range(1,N):
        memo[i] = memo[i-1]
        if i&1 and E[(i+1)//2] and E[i]:
            memo[i] += 1
            # print(i)
    # print(E[:12])
    # print(memo[:12])
    Q = I()
    for _ in range(Q):
        l,r = MI()
        # print("r",r)
        ans = memo[r] - memo[l-1]
        # print(memo[r] ,memo[l-1])
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def searchPrimeNumber(N):
    N = N + 1
    is_prime = np.ones(N, dtype=bool)
    is_prime[:2] = 0
    N_max = int(np.sqrt(N))
    for j in range(2, N_max+1):
        if (is_prime[j]):
            is_prime[j*j::j] = False
    prime = np.arange(N)[is_prime]
    return prime


def main():
    Q = int(readline())
    m = map(int, read().split())
    LR = list(zip(m, m))
    A = searchPrimeNumber(10**5)
    B = np.zeros(10**5+3, dtype=np.int32)  # Bはゼロ始まり
    for a in A:
        if (a + 1) / 2 in A:
            B[a+1:] += 1  # like 2017の数より１つ大きい数から1増やす

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


main()

Submission status: Accepted

Solution code:

# ほんとうに全ての値を最初に計算し、累積和のリストを作成してしまおう。
# 計算時間は421msでOKだけど、答えが間違っている。＝＞なおした

import math

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


# 2017に似た数

def is_like2017(n):
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False


Q = int(input())

l_list = [0]*Q
r_list = [0]*Q

for i in range(Q):
    l_list[i], r_list[i] = map(int, input().split())
    

ans = [0]

for i in range(1, 100000+1):
    if i % 2 == 0:
        ans.append(ans[i-1])
    elif is_like2017(i):
        ans.append(ans[i-1] + 1)
    else:
        ans.append(ans[i-1])    
        
for i in range(Q):
    print(ans[r_list[i]]-ans[l_list[i]-1])

Submission status: Accepted

Solution code:
# 全てを先に計算しておき、累積和を使って結果を表示する。 今度コソ累積和
# それにより、同じ計算を何度もしなくてすむ。最大10^5になるはず。
# 

import math
from itertools import accumulate

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


# 2017に似た数

def is_like2017(n):
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False


Q = int(input())

l_list = [0]*Q
r_list = [0]*Q

for i in range(Q):
    l_list[i], r_list[i] = map(int, input().split())
    
min_value = min(l_list)
max_value = max(r_list)

ans = []

for i in range(min_value, max_value+1):
    if i % 2 == 0:
        ans.append(0)
    elif is_prime(i) and is_like2017(i):
        ans.append(1)
    else:
        ans.append(0)

ans = [0] + list(accumulate(ans))        
        
for i in range(Q):
    print(ans[r_list[i]-min_value+1]-ans[l_list[i]-min_value])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def is_prime(n):
    i = 3
    while i <= n**0.5:
        if not n % i: return False
        i += 2

    return True

def main():
    prime = [2]
    prime_2017 = [0] * (10**5+1)
    
    for i in range(3, 10**5+1):
        prime_2017[i] = prime_2017[i-1]
        if not i % 2: continue
    
        if is_prime(i): prime.append(i)
        else: continue
        if (i+1)//2 in prime: prime_2017[i] += 1
    
    for i in range(int(input())):
        l, r = map(int, input().split())
        
        print(prime_2017[r] - prime_2017[l-1])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline


def eratosthenes(n):
    if n % 2 == 0:
        is_prime = [False, True] * (n // 2)
        is_prime.append(False)
    else:
        is_prime = [False, True] * ((n + 1) // 2)
    if n >= 1:
        is_prime[1] = False
    if n >= 2:
        is_prime[2] = True

    for i in range(3, n + 1, 2):
        if i * i > n:
            break
        if is_prime[i]:
            for j in range((n - i * i) // i + 1):
                is_prime[i * i + i * j] = False
    return is_prime


q = int(input())
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

r_max = max(r)
is_prime = eratosthenes(r_max)
a = [0] * (r_max + 1)
for i in range(3, r_max + 1):
    a[i] = a[i - 1]
    if is_prime[i] and is_prime[(i + 1) // 2]:
        a[i] += 1
# print(a)

for i in range(q):
    print(a[r[i]] - a[l[i] - 1])

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline


def eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, n + 1):
        if i * i > n:
            break
        if is_prime[i]:
            for j in range((n - i * i) // i + 1):
                is_prime[i * i + i * j] = False
    return is_prime


q = int(input())
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

r_max = max(r)
is_prime = eratosthenes(r_max)
a = [0] * (r_max + 1)
for i in range(3, r_max + 1):
    a[i] = a[i - 1]
    if is_prime[i] and is_prime[(i + 1) // 2]:
        a[i] += 1
# print(a)

for i in range(q):
    print(a[r[i]] - a[l[i] - 1])

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline


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


q = int(input())
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

r_max = max(r)
is_prime = eratosthenes(r_max)
a = [0] * (r_max + 1)
for i in range(3, r_max + 1):
    a[i] = a[i - 1]
    if is_prime[i] and is_prime[(i + 1) // 2]:
        a[i] += 1
# print(a)

for i in range(q):
    print(a[r[i]] - a[l[i] - 1])