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 itertools import accumulate


l = {79873, 3, 5, 45061, 90121, 13, 12301, 36877, 51217, 75793, 65557, 8221, 57373, 16417, 53281, 37, 36901, 38953, 51241, 22573, 18481, 36913, 20533, 63541, 88117, 41017, 47161, 61, 30781, 32833, 38977, 69697, 94273, 73, 6217, 4177, 34897, 55381, 2137, 10333, 22621, 14437, 82021, 43117, 49261, 57457, 88177, 94321, 10357, 18553, 61561, 8317, 12421, 30853, 75913, 28813, 65677, 71821, 12433, 53401, 84121, 157, 67741, 8353, 20641, 4261, 28837, 34981, 12457, 43177, 88237, 4273, 16573, 193, 6337, 43201, 67777, 26821, 88261, 18637, 24781, 55501, 80077, 26833, 63697, 10453, 6361, 61657, 6373, 82153, 94441, 96493, 49393, 61681, 69877, 16633, 28921, 47353, 12541, 14593, 26881, 4357, 41221, 96517, 12553, 24841, 49417, 8461, 33037, 16657, 277, 61717, 45337, 51481, 2341, 63781, 80173, 39217, 313, 12601, 43321, 51517, 41281, 8521, 26953, 78157, 55633, 86353, 82261, 4441, 65881, 84313, 67933, 74077, 80221, 18793, 31081, 94573, 78193, 20857, 45433, 72073, 397, 86413, 92557, 14737, 37273, 67993, 47521, 421, 61861, 2473, 45481, 63913, 29101, 47533, 12721, 98737, 51637, 59833, 49597, 27073, 88513, 41413, 78277, 457, 25033, 37321, 39373, 4561, 22993, 12757, 8677, 14821, 39397, 70117, 6637, 37357, 45553, 35317, 2557, 57853, 6661, 31237, 8713, 21001, 4621, 23053, 49681, 68113, 33301, 16921, 541, 55837, 2593, 70177, 47653, 12841, 45613, 76333, 12853, 43573, 94777, 25153, 21061, 43597, 74317, 10837, 31321, 80473, 92761, 47713, 613, 31333, 10861, 43633, 55921, 27253, 94837, 47737, 6781, 31357, 55933, 82561, 23173, 74377, 98953, 17041, 41617, 661, 25237, 92821, 64153, 70297, 17053, 53917, 673, 15013, 88741, 33457, 17077, 47797, 62137, 68281, 8893, 35521, 84673, 37573, 43717, 21193, 27337, 10957, 96973, 33493, 84697, 733, 92893, 15073, 27361, 2797, 64237, 47857, 757, 31477, 56053, 66301, 92941, 15121, 45841, 76561, 94993, 21277, 29473, 72481, 13093, 19237, 49957, 56101, 2857, 58153, 56113, 9013, 39733, 76597, 60217, 66361, 84793, 97081, 80701, 21313, 27457, 88897, 4933, 80713, 6997, 31573, 37717, 52057, 35677, 2917, 70501, 11113, 17257, 54121, 877, 52081, 54133, 64381, 56197, 15241, 17293, 7057, 11161, 97177, 88993, 41893, 54181, 72613, 68521, 93097, 9133, 15277, 60337, 84913, 46021, 29641, 54217, 91081, 93133, 99277, 76753, 5077, 60373, 25561, 74713, 9181, 33757, 70621, 17377, 997, 5101, 19441, 3061, 5113, 48121, 15361, 64513, 23557, 62473, 15373, 52237, 19477, 44053, 80917, 9241, 95257, 78877, 62497, 82981, 66601, 7213, 50221, 58417, 11317, 78901, 25657, 9277, 46141, 48193, 1093, 13381, 37957, 44101, 21577, 58441, 62533, 42061, 56401, 95317, 52321, 13417, 5233, 56437, 81013, 23677, 1153, 31873, 68737, 83077, 35977, 66697, 87181, 3217, 54421, 21661, 40093, 50341, 21673, 33961, 58537, 95401, 1201, 3253, 46261, 1213, 44221, 62653, 72901, 50377, 58573, 64717, 89293, 48337, 1237, 87253, 23773, 60637, 97501, 7393, 44257, 52453, 11497, 72937, 31981, 3313, 40177, 54517, 91381, 7417, 99577, 36097, 91393, 19717, 44293, 75013, 34057, 70921, 54541, 40213, 52501, 83221, 97561, 81181, 83233, 5413, 66853, 1321, 87337, 85297, 7477, 62773, 93493, 21817, 5437, 60733, 58693, 70981, 25933, 99661, 77137, 85333, 19801, 27997, 95581, 42337, 1381, 19813, 23917, 7537, 13681, 15733, 91513, 56701, 75133, 87421, 9601, 95617, 42373, 38281, 69001, 87433, 36241, 54673, 19861, 28057, 11677, 66973, 26017, 34213, 1453, 32173, 75181, 11701, 73141, 3517, 9661, 54721, 56773, 93637, 5581, 85453, 69073, 17881, 87517, 34273, 95713, 30181, 79333, 83437, 67057, 97777, 56821, 9721, 95737, 79357, 87553, 60937, 97813, 56857, 15901, 24097, 30241, 48673, 99877, 38461, 56893, 71233, 5701, 7753, 22093, 34381, 52813, 36433, 67153, 1621, 9817, 18013, 13921, 36457, 13933, 81517, 48757, 1657, 32377, 52861, 61057, 50821, 28297, 48781, 3733, 65173, 16033, 83617, 9901, 59053, 71341, 18097, 79537, 26293, 71353, 54973, 67273, 73417, 26317, 50893, 34513, 18133, 85717, 1753, 93913, 52957, 61153, 98017, 81637, 28393, 89833, 32497, 57073, 9973, 40693, 83701, 7933, 18181, 73477, 57097, 46861, 65293, 55057, 32533, 12073, 18217, 42793, 79657, 30517, 91957, 59197, 83773, 89917, 26437, 77641, 18253, 61261, 79693, 1873, 63313, 69457, 94033, 53077, 59221, 30553, 73561, 44893, 96097, 24421, 57193, 40813, 30577, 61297, 8053, 69493, 53113, 12157, 18301, 20353, 26497, 65413, 18313, 49033, 92041, 1933, 46993, 59281, 6037, 67477, 57241, 65437, 96157, 24481, 8101, 63397, 87973, 94117, 47017, 71593, 30637, 85933, 38833, 4021, 96181, 6073, 36793, 79801, 81853, 30661, 1993, 75721, 16333, 59341, 12241, 42961, 67537, 51157, 4057, 65497, 18397, 73693, 2017, 22501, 6121, 30697, 6133, 16381}
a = list(accumulate([1 if i in l else 0 for i in range(10 ** 5 + 1)]))
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(a[r] - a[l - 1])

Submission status: Accepted

Solution code:
from itertools import accumulate


def get_primes_til(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** .5) + 1):
        if is_prime[i]:
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return {i for i in range(2, n + 1) if is_prime[i]}


N_MAX = 10 ** 5
primes = get_primes_til(N_MAX)
is_2017_like = list(accumulate([i in primes and (i + 1) // 2 in primes for i in range(N_MAX + 1)]))
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(is_2017_like[r] - is_2017_like[l - 1])

Submission status: Accepted

Solution code:
from itertools import accumulate


def get_primes_til(n):
    primes = [True] * (n + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, int(n ** .5) + 1):
        for j in range(2 * i, n + 1, i):
            primes[j] = False
    return {i for i in range(2, n + 1) if primes[i]}


N_MAX = 10 ** 5
primes = get_primes_til(N_MAX)
is_2017_like = list(accumulate([i in primes and (i + 1) // 2 in primes for i in range(N_MAX + 1)]))
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(is_2017_like[r] - is_2017_like[l - 1])

Submission status: Accepted

Solution code:
from itertools import accumulate


def get_primes_til(n):
    primes = [True] * (n + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, int(n ** .5) + 1):
        for j in range(2 * i, n + 1, i):
            primes[j] = False
    return primes


N_MAX = 10 ** 5
is_prime = get_primes_til(N_MAX)
is_2017_like = list(accumulate([1 if is_prime[i] and is_prime[(i + 1) // 2] else 0 for i in range(N_MAX + 1)]))
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(is_2017_like[r] - is_2017_like[l - 1])

Submission status: Accepted

Solution code:
from itertools import accumulate


def get_prime_numbers_til(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N_MAX = 10 ** 5
primes = get_prime_numbers_til(N_MAX)
is_2017_like = list(accumulate([1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(N_MAX + 1)]))
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(is_2017_like[r] - is_2017_like[l - 1])

Submission status: Accepted

Solution code:
from itertools import accumulate


def get_primes_til(n):
    primes = [True] * (n + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, int(n ** .5) + 1):
        for j in range(2 * i, n + 1, i):
            primes[j] = False
    return primes


N_MAX = 10 ** 5
primes = get_primes_til(N_MAX)
is_2017_like = list(accumulate([int(primes[i] and primes[(i + 1) // 2]) for i in range(N_MAX + 1)]))
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(is_2017_like[r] - is_2017_like[l - 1])

Submission status: Accepted

Solution code:
import math
primes = [True]*(10**5+1)
primes[0],primes[1] = False,False
cumsum = [0]*(10**5+1)

for i in range(2, int(math.sqrt(10**5)+1)):
  if primes[i]:
    j = 2
    while i*j <= 10**5:
      primes[i*j] = False
      j += 1

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

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

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, 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] and is_prime[(i+1)//2]]


d = primes(100000)
cumsum = [0]
for i in range(1, 100001):
    if i in d:
        cumsum.append(cumsum[-1] + 1)
    else:
        cumsum.append(cumsum[-1])

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

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

from math import sqrt
def prime(n):
    if n<2:
        return False
    for i in range(2,int(sqrt(n)+1)):
        if n%i==0:
            return False
    return True
n=10*5-1
dp=[0 for i in range(10**5//2)]
dp[0]=0
for i in range(1,10**5//2):
    odd=2*i+1
    if prime(i+1) and prime(odd):
        dp[i]=dp[i-1]+1
    else:
        dp[i]=dp[i-1]
q=I()
for i in range(q):
    a,b=MI()
    if a==1:
        print(dp[(b+1)//2-1])
    else:
        print(dp[(b+1)//2-1]-dp[(a+1)//2-2])

Submission status: Accepted

Solution code:
Q = int(input())

def pri(N):
  x = (N + 1) // 2
  root = int(N ** (1/ 2))
  for i in range(2, root + 1):
    if N % i == 0:
      return 0
    if (x > i) and (x % i == 0):
      return 0
  return 1
  
prime = [0] * (10 ** 5)# 0 ~ 10 ** 5 - 1, prime[1] = 0
for i in range(3, 10 ** 5):
  if i % 2 == 1:
    add = pri(i)
    prime[i] = prime[i - 2] + add
    
for i in range(Q):
  l, r = map(int, input().split())
  if l == 1:
    minus = 0
  else:
    minus = prime[l - 2]
  print(prime[r] - minus)
  #print(prime[r] - minus, prime[r], minus)
#print(prime[:15])
#print(pri(7))

Submission status: Accepted

Solution code:
Q = int(input())
lr_list = [[int(i) for i in input().split()] for i in range(Q)]

is_prime = [1 for i in range(10**5+1)]
is_prime[0] = is_prime[1] = 0
for i in range(10**5+1):
    if not is_prime[i]:
        continue
    for j in range(i*2, 10**5+1, i):
        is_prime[j] = 0
        
a = [0 for i in range(10**5+1)]
for i in range(10**5+1):
    if i % 2 == 0:
        continue
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] = 1
        
s = [0 for i in range(10**5+2)]
for i in range(10**5+1):
    s[i+1] = s[i] + a[i]
    
for i in range(Q):
    lr = lr_list[i]
    print(s[lr[1]+1] - s[lr[0]])

Submission status: Accepted

Solution code:
"""
10^5以下の素数を列挙しておく。
それをもとに、10^5以下の各整数以下の2017に似た数の個数のメモを作成する。
"""
#10^5以下の素数を列挙
prime = [1] * (100001)
prime[0] = 0
prime[1] = 0
for i in range(2,100001):
    if prime[i]:
        for j in range(i*i,100001,i):
            prime[j] = 0

memo = [0]*(100001)
for i in range(3,100001):
    memo[i] = memo[i-1]
    if prime[i] and prime[(i+1)//2]:
        memo[i] += 1

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

Submission status: Accepted

Solution code:
import math

q = int(input())
cnt = [0] * (5 * 10 ** 4)
cnt[1] = 1
cnt[2] = 2


def is_prime(n):
    visit = []
    if n % 2 == 0:
        return 0
    for i in range(3, 1 + math.ceil(n ** (0.5))):
        if i not in visit:
            if n % i == 0:
                return 0
            else:
                visit.append(i)
    return 1


for i in range(3, 5 * 10 ** 4):
    odd = 2 * i + 1
    if odd % 3 != 1 or (odd + 1) % 4 == 0:
        cnt[i] = cnt[i - 1]
    else:
        k = 0
        if is_prime(odd) and is_prime((odd + 1) // 2):
            k = 1
            # print(odd, is_prime(odd), is_prime((odd + 1) // 2))
        cnt[i] = cnt[i - 1] + k
cnt.append(0)
for i in range(q):
    l, r = map(int, input().split())
    print(cnt[(r - 1) // 2] - cnt[(l - 3) // 2])

Submission status: Accepted

Solution code:
import math
# import itertools
# from collections import deque
# from collections import defaultdict
# import heapq
# import sys
# import bisect
# import numpy as np
# from scipy.special import comb


def erastosthenes(num):
    input_list = [False if i % 2 == 0 else True for i in range(num)]
    input_list[0] = False
    input_list[1] = False
    input_list[2] = True
    sqrt = math.sqrt(num)

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

        if serial >= sqrt:
            prime_list = [i for i, b in enumerate(input_list) if b]
            return prime_list

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


def main():
    Q = int(input())
    l = [0] * (Q + 1)
    r = [0] * (Q + 1)
    for i in range(1, Q + 1):
        l[i], r[i] = map(int, input().split())

    prime_list = set(erastosthenes(10**5))
    count_list = [0] * (10**5 + 1)

    for i in range(1, 10**5 + 1):

        if not i % 2 == 0:
            i2 = (i + 1) / 2
            if i in prime_list and i2 in prime_list:
                count_list[i] = count_list[i - 1] + 1
            else:
                count_list[i] = count_list[i - 1]
        else:
            count_list[i] = count_list[i - 1]

    for q in range(1, Q + 1):
        ans = count_list[r[q]] - count_list[l[q] - 1]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
INF = float('inf')


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


N = 10 ** 5
P = set(prime_numbers(N))
# これが素数
# print(P)
P = [n for n in P if (n + 1) // 2 in P]
# 自身 + 1 //2 も素数であるもののみに絞る
# print(P)
a = [0] * (N + 1)
for n in P:
    # likenumberは1にする
    a[n] = 1
# 累積和に変換
a = list(accumulate(a))


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

Submission status: Accepted

Solution code:
import itertools

def sieve(n):
    is_prime = [True for _ in range(n)]
    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
  
prime = sieve(10**5)
acu = [0] * ((10**5)//2+5)
for i in range(1,(10**5)//2+5):
    k = (i-1) * 2 +1
    if k in prime and (k+1)//2 in prime:
        acu[i] = acu[i-1] + 1
    else:
        acu[i] = acu[i-1]

q = int(input())

for i in range(q):
    l,r = map(int,input().split())
    li = (l-1) // 2
    ri = (r-1) // 2
    print(acu[ri+1]-acu[li])

Submission status: Accepted

Solution code:
def prime(n):
    a = [1]*(n+1)
    a[0],a[1] = 0,0
    for i in range(2,int(n**(0.5))+1):
        j = 2
        while i*j <= 10**5:
            a[i*j] = 0
            j += 1
    return a

def like2017(a):
    c = [0]*(10**5+1)
    for i in range(3,10**5+1):
        if a[i]*a[(i+1)//2]:
            c[i] = 1
    return c

def ssum(c):
    s = [0]*(10**5+1)
    for i in range(2,10**5+1):
        s[i] = s[i-1]+c[i]
    return s

def s(lst,l,r):
    return lst[r]-lst[l-1]


q = int(input())
a = prime(10**5)
c = like2017(a)

ss = ssum(c)
for i in range(q):
    l,r = map(int,input().split())
    print(s(ss,l,r))

Submission status: Accepted

Solution code:
import itertools

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]]
    return is_prime

p_list = primes(101010)
cnt_list = [0] * 101010

for i in range(1, 101011, 2):
    if p_list[i] and p_list[(i + 1) // 2]:
        cnt_list[i] = 1

cnt_list = list(itertools.accumulate(cnt_list))

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

Submission status: Accepted

Solution code:
import math

#nの素数判定
def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

#[0, n]の範囲で素数を列挙
def prime_table(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    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] = 0
    return is_prime

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

table = prime_table(max(r))
s = [0] * (max(r)+1)
for i in range(1, max(r)+1):
    if table[i] == 1 and is_prime((i+1)//2):
        s[i] = s[i-1] + 1
    else:
        s[i] = s[i-1]
#print(table)
#print(s)
for i in range(q):
    ans = s[r[i]] - s[l[i]-1]
    print(ans)

Submission status: Accepted

Solution code:
def check_prime(k):
    '''
    素数の時1、合成数の時0を返す
    '''
    if k == 1:return 0
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:return 0
    return 1

q = int(input())
lr = []
l_min = 10 ** 9
r_max = 0
for i in range(q):
    l, r = map(int,input().split())
    lr.append((l, r))
    if l < l_min:l_min = l
    if r > r_max:r_max = r

pre_cal = [0] * (r_max - l_min + 2)
dic = {}#一度素数と判定したもの
for num in range(l_min, r_max + 1):
    pre_cal[num - l_min + 1] = pre_cal[num - l_min]
    if num % 2 == 0:continue
    if not check_prime(num):continue
    dic[num] = 1
    temp = (num + 1) // 2

    if dic.get(temp, 0):
        pre_cal[num - l_min + 1] = pre_cal[num - l_min + 1] + 1 if num != l_min else 1
    else:
        if check_prime(temp):
            dic[temp] = 1
            pre_cal[num - l_min + 1] = pre_cal[num - l_min + 1] + 1 if num != l_min else 1

for l, r in lr:
    ans = pre_cal[r - l_min + 1] - pre_cal[l - l_min]
    print(ans)

#print(pre_cal)

Submission status: Accepted

Solution code:
def get_prime(x):
    l = [True] * (x + 1)
    l[0] = False
    l[1] = False
    for i in range(2,int(x**0.5) + 1):
        if not l[i]:
            continue
        for j in range(i * 2, x + 1, i):
            l[j] = False
    return l        
q=int(input())
table = get_prime(100000)
s=[0]*(100001)

for i in range(100000):
    if table[i] and table[(i+1)//2]:
        s[i] = 1

for i in range(100000):        
    s[i+1] += s[i]

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}

def main():
    N = 10 ** 5
    primes = prime_numbers(N)
    a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
    a = tuple(accumulate(a))

    ans = []
    Q, *LR = map(int, open(0).read().split())
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(a[r] - a[l - 1])

    print('\n'.join(map(str, ans)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = tuple(accumulate(a))

ans = []
Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    ans.append(a[r] - a[l - 1])

print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = list(accumulate(a))

ans = []
Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    ans.append(a[r] - a[l - 1])

print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = list(accumulate(a))

ans = []
Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    ans.append(a[r] - a[l - 1])

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = list(accumulate(a))

Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    print(a[r] - a[l - 1])

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [n in primes and (n + 1) // 2 in primes for n in range(N + 1)]
a = list(accumulate(a))

Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    print(a[r] - a[l - 1])

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


N = 10 ** 5
P = set(prime_numbers(N))
P = [n for n in P if (n + 1) // 2 in P]
a = [0] * (N + 1)
for n in P:
    a[n] = 1
a = list(accumulate(a))

Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    print(a[r] - a[l - 1])

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


N = 10 ** 5
P = set(prime_numbers(N))
P = [n for n in P if (n + 1) // 2 in P]
a = [0] * (N + 1)
for n in P:
    a[n] = 1
a = list(accumulate(a))

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

Submission status: Accepted

Solution code:
def isPrime(x):
    if x < 2:
        return 0
    elif x == 2:
        return 1
    if x%2 == 0:
        return 0
    ir=int(x**(0.5))+1
    for i  in range(3,ir,2) :
        if x%i == 0:
            return 0
    return 1

q=int(input())

l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
    
ps=[0]
pcnt=0
for i in range(1,max(r)+1):
    if i%2==1 and isPrime(i) and isPrime((i+1)//2):
        pcnt+=1
    ps.append(pcnt)        

#print(ps)

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

Submission status: Accepted

Solution code:
from math import sqrt
from bisect import bisect_right

def eratos(n):
    L = [True for _ in range(n+1)]
    L[0],L[1] = False,False

    for i in range(2,int(sqrt(n))+1):
        if L[i]:
            for j in range(2,n//i+1):
                L[i*j] = False

    P = []
    for i in range(n+1):
        if L[i]:
            P.append(i)

    return P

def sim(P):
    #よく考えたら元の数より小さい数に対する判定
    #なのでisPrime関数を使うまでもない
    P_set = set(P)
    P_sim = []
    for i in range(len(P)):
        if (P[i]+1)//2 in P_set:
            P_sim.append(P[i])

    return P_sim

def main():
    Q = int(input())

    P = eratos(10**5)
    P_sim = sim(P)

    ans_L = []
    for i in range(Q):
        l,r = map(int,input().split())
        ans = bisect_right(P_sim,r)-bisect_right(P_sim,l-1)
        ans_L.append(ans)

    for i in range(Q):
        print(ans_L[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import sqrt
from bisect import bisect_right

def eratos(n):
    L = [True for _ in range(n+1)]
    L[0],L[1] = False,False

    for i in range(2,int(sqrt(n))+1):
        if L[i]:
            for j in range(2,n//i+1):
                L[i*j] = False

    P = []
    for i in range(n+1):
        if L[i]:
            P.append(i)

    return P

def isPrime(n):
    if n == 1:
        return False

    for i in range(2,int(sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def sim(P):
    #ソート済み素数リストを受け取って後半の条件も満たすやつのリストを計算
    P_sim = []
    for i in range(len(P)):
        if isPrime((P[i]+1)//2):
            P_sim.append(P[i])

    return P_sim

def main():
    Q = int(input())

    P = eratos(10**5)
    P_sim = sim(P)

    ans_L = []
    for i in range(Q):
        l,r = map(int,input().split())
        ans = bisect_right(P_sim,r)-bisect_right(P_sim,l-1)
        ans_L.append(ans)

    for i in range(Q):
        print(ans_L[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

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

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

Submission status: Accepted

Solution code:
def main():

    def hurui():
        N = 10 ** 5
        p = [1] * (N+1)
        p[0], p[1] = 0, 0
        for i in range(4, N+1, 2): p[i] = 0
        for i in range(3, N+1):
            if i * i > N: break
            if p[i]:
                for j in range(i, N+1):
                    if i*j > N: break
                    p[j*i] = 0
        return p

    p = hurui()
    q = [0] * (10**5+1)
    for i in range(1, 10 ** 5 + 1):
        if i%2 == 0: continue
        if p[i] and p[(i+1)//2]: q[i] = 1
    r = [0] * (10**5+2)
    for i in range(10**5+1):
        r[i+1] = r[i] + q[i]

    Q = int(input())
    query = [[int(_) for _ in input().split()] for __ in range(Q)]
    for a, b in query:
        print(r[b+1] - r[a])
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
事前に、100000以下の数のうち、2017に似た数を列挙しておく。
メモの仕方としては、2017に似た数を小さい順に並べておけばよい。
2017に似た数を探すのは、まず100000以下の素数を全部列挙して、その中で条件に当てはまるものを愚直に探す。
"""
memo = [1]*(100001)
memo[0] = 0
memo[1] = 0
primes = set()
for i in range(100001):
    if memo[i] == 1:
        primes.add(i)
        for j in range(i*2,100001,i):
            memo[j] = 0

answers = []
for p in primes:
    if (p+1)//2 in primes:
        answers.append(p)

Q = int(input())
for _ in range(Q):
    ans = 0
    l,r = map(int,input().split())
    for a in answers:
        if l<=a<=r:
            ans += 1
    print(ans)