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

primes=[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]
# primesset=set(primes)

Q=int(input())
res=[0]*Q
for i in range(Q):
    l,r=map(int,input().split())
    p = bisect_left(primes, l)
    q = bisect_right(primes, r)
    res[i]=q-p

for cnt in res:
    print(cnt)

Submission status: Accepted

Solution code:
from itertools import accumulate
q=int(input())
lr=[list(map(int,input().split())) for i in range(q)]
p=[2]
pc=[0]*100001
pc[2]=1
ans=[0]*100001
for i in range(3,100001):
  for j in p:
    if(i%j==0):
      break
    if(j*j>i):
      p.append(i)
      pc[i]=1
      if(pc[i//2+1]==1):
        ans[i]=1
      break
ans=list(accumulate(ans))
for l,r in lr:
  print(ans[r]-ans[l-1])

Submission status: Accepted

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

def eratos(n :int):
    # initialize
    isprime = [True] * (n+1)
    isprime[0] = isprime[1] = False

    for i in range(2, int(math.sqrt(n)+1)):
        if(isprime[i]):
            j = i+i
            while(j <= n):
                isprime[j] = False
                j = j+i

    return isprime

def solve(Q: int, l: "List[int]", r: "List[int]"):
    myo = eratos(100000)
    rodd = [0]*100001

    r2017 = [False]*100001
    for i in range(1,100001):
        if(i%2 == 0):
            continue
        elif(myo[i] and myo[int((i+1)/2)]):
            r2017[i] = True

    for i in range(2,100001):
        rodd[i] = rodd[i-1] +(1 if r2017[i-1] else 0)

    # for i in range(20):
    #     print(i,rodd[i])
        


    # たぶんここからがミス
    ans = [0]*Q
    for i in range(Q):
        ans[i] = rodd[r[i]+1] - rodd[l[i]]

    for i in ans:
        print(i)

    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
Q = int(input())
lr = list(list(map(int,input().split())for i in range(Q)))
pn = [0,0]+[1]*(10**5-2)
O = 0
for i in range(2,317):
    for j in range(i*2,10**5,i):
        pn[j] = 0
p = pn.copy()
for i in range(7,10**5):
    if p[i]==1:
        if(pn[int((i+1)/2)]==0):
            p[i] = 0
tmp = 0
p[2] =0
for i in range(10**5):
    p[i] = tmp+p[i]
    tmp = p[i]
for l,r in lr:
    print(p[r]-p[l-1])

Submission status: Accepted

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

def prime_table(n):
    list = [True for _ in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        if list[i]:
            j = i*2
            while j<=n:
                list[j] = False
                j += i
    table = [i for i in range(n+1) if list[i] and i>=2]
    return table

table = prime_table(10**5)
table_set = set(table)
sim_sum = [0]*(10**5+1)

for p in table:
    if p*2-1 in table_set:
        sim_sum[p*2-1] += 1
for i in range(1,10**5+1):
    sim_sum[i] += sim_sum[i-1]
for l_ in l:
    print(sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)])

Submission status: Accepted

Solution code:
def prime_table(n):
    memo = [True for _ in range(n + 1)]
    i = 2
    while i * i <= n:
        if memo[i]:
            j = i + i
            while j <= n:
                memo[j] = False
                j += i
        i += 1
    return memo

memo = prime_table(10 ** 5)
A = [0 for _ in range(10 ** 5 + 1)]
for i in range(3, 10 ** 5 + 1, 2):
    if memo[i] and memo[(i + 1) // 2]:
        A[i] += 1
for i in range(3, 10 ** 5 + 1):
    A[i] += A[i - 1]

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

Submission status: Accepted

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

def prime_table(n):
    list = [True for _ in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        if list[i]:
            j = i*2
            while j<=n:
                list[j] = False
                j += i
    table = [i for i in range(n+1) if list[i] and i>=2]
    return table

table = prime_table(10**5)
sim_sum = [0]*(10**5+1)

for i in range(len(table)):
    if table[i]*2-1 in table:
        sim_sum[table[i]*2-1] += 1
for i in range(1,10**5+1):
    sim_sum[i] += sim_sum[i-1]
for l_ in l:
    print(sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)])

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    q = []
    for i in range(0, n):
        q.append([int(x) for x in input().split()])

    is_prime = eraatosthenes()

    a = []
    for i in range(0, 100000):
        a.append(0)

    for i in range(0, len(is_prime)):
        if i % 2 == 0:
            continue
        if is_prime[i] == 1 and is_prime[int((i + 1) / 2)] == 1:
            a[i] = 1

    s = [0]
    for i in range(0, len(a)):
        s.append(s[i] + a[i])

    for i in range(0, len(q)):
        l, r = q[i][0], q[i][1]
        print(s[r+1] - s[l])


def eraatosthenes():
    list = []
    for i in range(0, 100000):
        list.append(0)

    for i in range(2, len(list)):
        list[i] = 1

    for i in range(2, len(list)):
        if list[i] == 1:
            j = i * 2
            while j < len(list):
                list[j] = 0
                j += i
    return list

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

mc = 0
for v in l:
    mc = max(mc, v[1])
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]

for t in l:
    x, y = t[0], t[1]
    p = 0
    if 0 <= x - 1:
        p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Accepted

Solution code:
MAX=100000
isprime=[1]*(MAX+1)
isprime[0]=0
isprime[1]=0

for i in range(2,int(pow(MAX,0.5)+1)):
    if isprime[i]==1:
        for j in range(i*2,MAX+1,i):
            isprime[j]=0

islike2017=[0]*(MAX)
for i in range(MAX):
    if isprime[i]==1 and isprime[int((i+1)/2)]==1:
        islike2017[i]=1

cumsum=[0]*(MAX+1)
for i in range(1,MAX+1):
    cumsum[i]=cumsum[i-1]+islike2017[i-1]

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

Submission status: Accepted

Solution code:
MAX=114514

v = [0]*MAX
p = [1]*MAX
p[0] = p[1] = 0

for i in range(int(MAX**0.5)+1):
	if p[i] == 1:
		n = i + i
		while n < MAX:
			p[n] = 0
			n += i

for i in range(1, MAX):
	v[i] = v[i-1]
	if p[i] == 1:
		v[i] += p[(i+1)//2]

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

Submission status: Accepted

Solution code:
"""
primes=set()
like=set()

for n in range(2, 10**5):
	for p in primes:
		if n % p == 0:
			n = -1
			break
	if n != -1:
		primes.add(n)
		if (n+1)//2 in primes:
			like.add(n)
"""
like = 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])

v = [0]*(10**5+9)
for i in range(1, 10**5+9):
	v[i] = v[i-1] + (1 if i in like else 0)

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

Submission status: Accepted

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

prime = [2]
l = len(prime)
p = prime[-1]+1

d = [0] * 100002

def isPrime(x):
    i = 0
    while i < l:
        if prime[i]**2 > x:
            return True
        if not(x % prime[i]):
            return False
        i += 1

while p < 100000:
    if isPrime(p):
        prime.append(p)
        d[p] = 1
        l += 1
    p += 1

a = [0,1]

for i in range(5,100002,2):
    b = d[i] and d[(i+1)//2]
    a.append(a[-1]+b)

o = []
for i in lr:
    if i[1] == 1:
        o.append(0)
        continue
    if i[0] == 1:
        i[0] = 3
    i[0] = (i[0] - 1)//2
    i[1] = (i[1] - 1)//2
    o.append(a[i[1]]-a[i[0]-1])
    
print('\n'.join(map(str,o)))

Submission status: Accepted

Solution code:
import math

def eratosthenes():
    limit = 100001
    B = [True for _ in range(limit + 1)]
    C = [0 for i in range(limit + 1)]
    for i in range(2, limit):
        if i >= math.sqrt(limit):
            break
        for ii in range(i ** 2, limit, i):
            B[ii] = False
    for i in range(3, limit + 1, 2):
        if B[i] and B[(i + 1) // 2]:
            C[i] += 1
    for i in range(3, limit + 1):
        C[i] += C[i - 1]
    return C


def main():
    Q = int(input())
    C = eratosthenes()
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(C[r] - C[l - 1])
    for c in ans:
        print(c)


main()

Submission status: Accepted

Solution code:
import math

def eratosthenes():
    limit = 100001
    A = [i for i in range(2, limit)]
    B = [False for _ in range(limit + 1)]
    C = [0 for i in range(limit + 1)]
    while True:
        a = min(A)
        if a > math.sqrt(limit):
            break
        B[a] = True
        i = 0
        while len(A) > i:
            if A[i] % a == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        B[a] = True
    for i in range(3, limit + 1, 2):
        if B[i] and B[(i + 1) // 2]:
            C[i] += 1
    for i in range(3, limit + 1):
        C[i] += C[i - 1]
    return C


def main():
    Q = int(input())
    C = eratosthenes()
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(C[r] - C[l - 1])
    for c in ans:
        print(c)


main()

Submission status: Accepted

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

from itertools import accumulate

import math

def is_prime(n):
    if n <= 0: return None
    if n == 1: return False
    sup = math.floor(pow(n,1/2))
    for i in range(2,sup+1):
        if n % i == 0:
            return False
    return True

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

bit = [0]*(10**5+1)

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

bit = list(accumulate(bit))

for l, r in query:
    res = bit[r] - bit[l-1]
    print(res)

Submission status: Accepted

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

def half(odd):
    return (odd + 1) // 2


class cPrimes:
    def __init__(self, N):
        self.N = N
        self.L = N // 96 + 1
        self.sieve()
    
    def sieve(self):
        self.bits = [ -1 ] * self.L
        for p in itertools.takewhile(lambda p: p * p < self.N,
                            itertools.islice(self.enumerate(), 2, None)):
            k0 = p // 3
            for k in range(k0 + p * 2, self.N // 3 + 1, p * 2):
                self.erase_bit(k)
            for k in range(-k0 - 1 + p * 2, self.N // 3 + 1, p * 2):
                self.erase_bit(k)
    
    def enumerate(self):
        yield 2
        yield 3
        k0 = 1
        for m, B in enumerate(self.bits):
            for k in range(k0, 32):
                if ((B >> k) & 1) == 1:
                    yield m * 96 + k * 3 + 1 + (k & 1)
            k0 = 0
    
    def is_prime(self, n):
        if n < 4:
            return n >= 2
        else:
            q, r = divmod(n, 6)
            if r == 1:
                k = q >> 4
                l = (q & 15) << 1
                return ((self.bits[k] >> l) & 1) == 1
            elif r == 5:
                k = q >> 4
                l = ((q & 15) << 1) + 1
                return ((self.bits[k] >> l) & 1) == 1
            else:
                return False
    
    def erase_bit(self, k):
        m = k >> 5 # 6bit目以降
        l = k & 31 # 5bit目まで
        if l != 31:
            self.bits[m] &= ~(1 << l)
        else:
            self.bits[m] &= ~(-1 << 31)


def solve(Q: int, l: "List[int]", r: "List[int]"):
    limit = max(r)
    like2017_count = [0 for i in range(half(limit)+1)]
    cp = cPrimes(limit)

    for i in range(1, half(limit)+1):
        if cp.is_prime(i) and cp.is_prime(i * 2 - 1):
            like2017_count[i] = like2017_count[i-1] + 1
        else:
            like2017_count[i] = like2017_count[i-1]
    
    for q in range(Q):
        print(like2017_count[half(r[q])] - like2017_count[half(l[q])-1])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
Q = int(input())
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
MAX = 10**5
sum = [0] * (MAX+2)

is_prime = [1] * (MAX+1)
is_prime[0] = 0
is_prime[1] = 0
for i in range(2, MAX+1):
    if is_prime[i]:
        for j in range(i*2, MAX+1, i):
            is_prime[j] = 0

for i in range(MAX+1):
    if is_prime[i] and is_prime[(i+1)//2]:
        sum[i+1] = sum[i] + is_prime[i]
    else:
        sum[i+1] = sum[i]
        
for i in range(Q):
    print(sum[r[i]+1] - sum[l[i]])

Submission status: Accepted

Solution code:
sieve = [True] * 100001
#one-based-index
def mark(sieve,x):
    for i in range(x+x,len(sieve),x):
        sieve[i] = False

for x in range(2,int(len(sieve) ** 0.5) + 1):
    if sieve[x]: mark(sieve,x)

sieve[0] = False
sieve[1] = False

for i in range(len(sieve)-2,2,-2):
    if sieve[i]:
        if not(sieve[(i+1)//2]):
            sieve[i] = False #2017likeでない

sieve[2] = False

cnt = [0] * 100002
for i,s in enumerate(sieve):
    if s:
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]

q = int(input())

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

Submission status: Accepted

Solution code:
import numpy as np

U = 10**5
is_prime = np.full(U+1,True)
is_prime[:2] = False
for p in range(2,U+1):
  if p*p > U:
    break
  if is_prime[p]:
    is_prime[p*p::p] = False

sophy = np.zeros(U+1,dtype = np.int32)
for p in range(1,U+1):
  if 2*p > U:
    break
  if is_prime[p] and is_prime[2*p-1]:
    sophy[2*p-1] = 1

sophy_cnt = sophy.cumsum()

# 入力に対応ここから
Q = int(input())
for i in range(Q):
  l,r = map(int,input().split())
  ans = sophy_cnt[r] - sophy_cnt[l-1]
  print(ans)

Submission status: Accepted

Solution code:
def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check p+1 ~ p^2-1 (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return prime

Q = int(input())
primes = sieve_of_eratosthenes(10**5)
cum_sum = [0]*(10**5+1)
for i in range(1, 10**5+1):
    if primes[i] and primes[(i+1) // 2]:
        cum_sum[i] = cum_sum[i-1] + 1
    else:
        cum_sum[i] = cum_sum[i-1]

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

Submission status: Accepted

Solution code:
#D問題
import math
def isprime(n):
    nroot=int(math.sqrt(n))
    flag=0
    for i in range(2,nroot+1):
        if n%i == 0:
            flag=1
            break
    return flag
Q=int(input())
L=[]
R=[]
for i in range(Q):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)
Rmax=max(R)
pcount=[]
for i in range(Rmax):
    I=i+1
    if I == 1:
        pcount.append(0)
    elif I%2 == 1:
        pf=pcount[-2]
        if isprime(I) == 0 and isprime(int((I+1)/2)) == 0:
            pf+=1
        pcount.append(pf)
    else:
        pcount.append(0)
for i in range(Q):
    ans=pcount[R[i]-1]-pcount[L[i]-3]
    print(ans)

Submission status: Accepted

Solution code:
def isPrime(n):
    for p in primes:
        if n%p == 0:
            return False
        elif n < p*p:
            return True

primes = [2,3,5,7]
for i in range(11,10**5,2):
    if isPrime(i):
        primes.append(i)
n2017s = [0]
for p in primes[1:]:
    if (p+1)//2 in primes:
        n2017s.append(p)
n2017s.append(10**6)
        
def binary_search(n):
    l=0
    r=len(n2017s)-1
    while l+1<r:
        i = (l+r)//2
        if n2017s[i] > n:
            r = i
        else:
            l = i
    return l

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

Submission status: Accepted

Solution code:
import bisect


def searchPrimeNum(N):
    max = int(N**(1/2))
    seachList = [i for i in range(2, N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


list1 = searchPrimeNum(100000)
list2 = list(map(lambda x: 2 * x - 1, list1))
li = list(set(list1) & set(list2))
li.sort()
for i in range(int(input())):
    l, r = map(int, input().split())
    print(bisect.bisect_right(li, r) - bisect.bisect_left(li, l))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import math
def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

if __name__ == '__main__':
    Q = int(input())
    
    input_list = sieve_of_erastosthenes(100010)
    
    li = []
    
    cnt=0
    li.append(cnt)
    for i in range(1, 100010):
        if int(i)%2 == 1:
            if input_list[int(i)] == True and input_list[int((i+1)/2)] == True:
                cnt = cnt+1
                
        li.append(cnt)
    
    
    for i in range(Q):
        l,r = map(int, input().split())
        print(li[r]-li[l-1])

Submission status: Accepted

Solution code:
def witness(a,n,t,u):
    x=pow(a,u,n)
    for _ in range(t):
        y=(x*x)%n
        if y==1 and x!=1 and x!=(n-1):
            return True
        x=y
    return y!=1

def is_probably_prime(n,witnesses):
    t=1
    u=n>>1
    while u&1==0:
        t+=1
        u>>=1
    assert(2**t*u==n-1)
    for a in witnesses:
        if a<n and witness(a,n,t,u):
            return False
    return True

def is_definitely_prime(n):
    if ((not (n&1)) and n!=2) or (n<2) or ((n%3==0) and (n!=3)):
        return False
    elif n<=3:
        return True
    else:
        return is_probably_prime(n,[2,7,61])

n=10**5
P=[0]*(n+1)
for i in range(n):
    if is_definitely_prime(i+1) and is_definitely_prime((i+2)//2):
        P[i+1]=P[i]+1
    else:
        P[i+1]=P[i]
q=int(input())
Q=[tuple(map(int,input().split())) for _ in range(q)]
for l,r in Q:
    ans=P[r]-P[l-1]
    print(ans)

Submission status: Accepted

Solution code:
import math

def is_prime(n):
    if n == 1:
        return False
    if not isinstance(n,int):
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

Q=int(input())
L,R=[],[]
for i in range(Q):
    l,r = list(map(int,input().split()))
    L.append(l)
    R.append(r)

list_2017_similar_num=[0]
for i in range(1,100001):
    if i % 2 == 0:
        list_2017_similar_num.append(list_2017_similar_num[i-1])
    else:
        if is_prime(i) == True and is_prime(int((i+1)/2)) == True:
            list_2017_similar_num.append(list_2017_similar_num[i-1]+1)
        else:
            list_2017_similar_num.append(list_2017_similar_num[i-1])

for i in range(Q):
    print(list_2017_similar_num[R[i]] - list_2017_similar_num[L[i]-1])

Submission status: Accepted

Solution code:
def net(end_num):
    if end_num < 2:
        return []
    primes = [2]
    nums = list(range(3, end_num, 2))
    while nums:
        primes.append(nums[0])
        nums = [n for n in nums if n % nums[0]]
    return primes

cumsum = [0, 0, 0]
sum_val = 0
primes = net(330)
for n in range(3, 100001):
    like_2017 = True
    for p in primes:
        if (n % p == 0) and (n > p):
            like_2017 = False
            break
        if (((n + 1) // 2) % p == 0) and (((n + 1) // 2) > p):
            like_2017 = False
            break
    sum_val += like_2017
    cumsum.append(sum_val)
    
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(cumsum[r] - cumsum[l - 1])