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 sys import stdin
def main():
  from math import sqrt
  readline = stdin.readline
  p = [True] * (10 ** 5 + 1)
  p[0] = False
  p[1] = False
  n = int(sqrt(10 ** 5)) + 1
  for j in range(4, 10 ** 5 + 1, 2):
    p[j] = False
  for i in range(3, n + 1, 2):
    if p[i]:
      for j in range(i + i, 10 ** 5 + 1, i):
        p[j] = False
  c = [0] * (10 ** 5 + 2)
  for i in range(2, 10 ** 5 + 2):
    c[i] = c[i - 1]
    if p[i - 2] and p[(i - 1) // 2]:
      c[i] += 1
  q = int(readline())
  for _ in range(q):
    l, r = map(int, readline().split())
    print(c[r + 2] - c[l + 1])
main()

Submission status: Accepted

Solution code:

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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]]

N = 10 ** 5 
primelist = primes(10**5)
prime_add = [0] * (10**5+1)
idx = 0
i = 1
import bisect
L = len(primelist)

while idx < L:
    if i == primelist[idx]:
        tmp = bisect.bisect_right(primelist,(i+1)//2)
        if primelist[tmp-1] == (i+1)//2:
            prime_add[i] = prime_add[i-1] + 1
        else:
            prime_add[i] = prime_add[i-1]
        i += 1
        idx += 1
    else:
        prime_add[i] = prime_add[i-1]
        i += 1
while i < N+1:
    prime_add[i] = prime_add[i-1]
    i += 1
        

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

for l,r in lr:
    print(prime_add[r]-prime_add[l-1])

Submission status: Accepted

Solution code:
import math

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]


# まずは素数表を作る
ten5 = 10**5

# x = 素数一覧
x = get_sieve_of_eratosthenes(ten5)

# P = 素数表(1 = 素数)
P = [0] * (ten5+1)

# LIKE = 似た数表
LIKE = [0] * (ten5+1)
for i in x:
    P[i] = 1

    if i == 2:
        LIKE[i] = 1
        continue

    # i は素数
    like = ((i+1)//2)
    LIKE[i] = P[like]

S = [0] * (ten5+1)
S[0] = LIKE[0]
for i in range(1, ten5+1):
    S[i] = S[i-1] + LIKE[i]


Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())

    ans = S[r]-S[l-1]
    if l <= 1:
        ans -= 1

    print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
q = int(input())

primes = {i for i in range(2,10**5 + 1)}
for i in range(2,int(sqrt(10**5+1)) + 1):
    if i in primes:
        mul = 2
        while i*mul <= 10**5:
            primes.discard(i*mul)
            mul += 1

ret = [0]*(1 + 10**5)
for i in range(3,1 + 10**5):
    if i&1:
        if i in primes and (i+1)/2 in primes:
            ret[i] = ret[i-1] + 1
        else:
            ret[i] = ret[i-1]
    else:
        ret[i] = ret[i-1]

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

Submission status: Accepted

Solution code:
N = 100005
primes = [True]*N
primes[0] = False
primes[1] = False
for i in range(2,N):
  for j in range(i+i,N,i):
    primes[j] = False
#print(primes)

likenums = [False]*N
for k in range(1,N,2):
  likenums[k] = (primes[k] and primes[(k+1)//2])

integ = [0]*N
for k in range(1,N):
  integ[k] = integ[k-1]+(1 if likenums[k] else 0)
#print(integ)

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

Submission status: Accepted

Solution code:
Q = int(input())

def isPrime(p):
    for i in range(2, int(p**0.5)+1):
        if p % i == 0:
            return False
    return True

F = [1]*(10**5+1)
F[0], F[1] = 0, 0
for j in range(2, len(F)):
    if isPrime(j) == True:
        for k in range(j*2, len(F), j):
            F[k] = 0

for e in range(2, len(F))[::-1]:
    if F[e] == 1 and (e) % 2 == 1:
        if F[int((e+1)/2)] == 0:
            F[e] = 0
    else:
        F[e] = 0

t = [0]*len(F)
for a in range(len(F)-1):
    t[a+1] = t[a] + F[a]

for b in range(Q):
    l, r = map(int, input().split(" "))
    print(t[r+1] - t[l])

Submission status: Accepted

Solution code:
import numpy as np

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

q=int(input())
lr=[[int(x) for x in input().split()] for _ in range(q)]

primelist=[0,]*(100000+1)
for n in primes(100000):
  primelist[n]=1

list2017=[primelist[n] and primelist[(n+1)//2] for n in range(1,100000,2)]
cumsum=np.cumsum(list2017)
for query in lr:
  print(cumsum[(query[1]-1)/2]-cumsum[max(0,(query[0]-1)/2-1)])

Submission status: Accepted

Solution code:
def primes():
    """
    素数のジェネレータ
    """
    d = {}
    q = 2
    while True:
        if q not in d:
            yield q
            d[q * q] = [q]
        else:
            for p in d[q]:
                d.setdefault(p + q, []).append(p)
            del d[q]
        q += 1

p = set()
for num in primes():
    if num > 100001:
        break
    p.add(num)

memo = [0 for _ in range(100001)]
for i in range(1, 100001):
    if i % 2 == 0:
        memo[i] = memo[i - 1]
        continue
    if i in p and (i + 1) // 2 in p:
        memo[i] = memo[i - 1] + 1
    else:
        memo[i] = memo[i - 1]

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

Submission status: Accepted

Solution code:
import math
import bisect


# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=100000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
l = callIsPrime(100000)
#print(l)
#print(len(l))

ll = []
for i in range(len(l)):
    if (l[i]+1)//2 in l:
        ll.append(l[i])


Q = int(input())
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
for i in range(Q):
    a = bisect.bisect_left(ll,l[i])
    b = bisect.bisect_right(ll,r[i])
    print(b-a)

Submission status: Accepted

Solution code:
from itertools import accumulate

sim = {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}
S = [0] * 100010
for s in sim:
    S[s] = 1
T = list(accumulate(S))

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