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:
import numpy as np


def solve():
    n = 10**5+1
    like = np.zeros(n, dtype='uint64')
    like[2] = 0

    p = [True] * (n)
    p[0] = False
    p[1] = False
    for i in range(4, n, 2):
        p[i] = False

    for j in range(3, n, 2):
        q = (j+1)//2
        if p[j]:
            for k in range(j*2, n, j):
                p[k] = False
            if p[q]:
                like[j] = 1
            else:
                like[j] = 0
        else:
            like[j] = 0

    return np.cumsum(like)


if __name__ == '__main__':
    q = int(input())
    accum = solve()
    for l in range(q):
        l, r = map(int, input().split())
        print(accum[r]-accum[l-1])

Submission status: Accepted

Solution code:
import math
from collections import defaultdict


def SieveofEratosthenes(N):
    if N < 2:
        raise ValueError('N should be more than 2')
    primeList = []
    limit = math.sqrt(N)
    data = [i + 1 for i in range(1, N)]
    while True:
        p = data[0]
        if limit <= p:
            return primeList + data
        primeList.append(p)
        data = [e for e in data if e % p != 0]


Q = int(input())
primeList = SieveofEratosthenes(10**5)
primeDict = defaultdict(int)
like2017Dict = defaultdict(int)
for p in primeList:
    primeDict[p] = 1
for p in primeList:
    if primeDict[(p+1)//2] == 1:
        like2017Dict[p] = 1

numPrimes = [0 for i in range(10**5+1)]
for i in range(3, 10**5+1):
    if like2017Dict[i] == 1:
        numPrimes[i] = numPrimes[i-1] + 1
    else:
        numPrimes[i] = numPrimes[i-1]


def solve(l, r):
    ans = numPrimes[r] - numPrimes[l-1]
    return ans


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

Submission status: Accepted

Solution code:
import math
def is_prime(n):
    if n == 2 or n == 3: return True
    if n < 2 or n%2 == 0: return False
    if n < 9: return True
    if n%3 == 0: return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        if n%f == 0: return False
        if n%(f+2) == 0: return False
        f +=6
    return True 

def resolve():
    Q = int(input())
    LRs = [list(map(int, input().split(" "))) for i in range(Q)]
    N = 10**5
    
    # 2017に似た数なら1になる数列を生成 O(10^5)
    isSpecial = [0] * (N+1)
    for i in range(1, N+1, 2):
        if is_prime(i) and is_prime((i+1)/2):
            isSpecial[i] = 1
    
    # 累積和を計算 O(10^5)
    sums = [0] * (N+1)
    for j in range(0, N+1):
        sums[j] = sums[j-1] + isSpecial[j]

    # クエリ処理 O(Q)
    for (l, r) in LRs:
        print(sums[r+1] - sums[l-1])
        

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect,bisect_left
def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime
prime = eratosthenes(10**5)
p_d = defaultdict(lambda:0)
prime17 = []
for p in prime:
    p_d[p] = 1
for p in prime:
    if p_d[(p+1)/2] == 1:
        prime17.append(p)

Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    l = bisect_left(prime17,l)
    r = bisect(prime17,r)
    print(r-l)

Submission status: Accepted

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

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

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

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

    return set(prime for prime in primes if prime != 0)


def is_prime(prime_list,a):
    return a in prime_list

def solve(Q: int, L: "List[int]", R: "List[int]"):
    prime_list = primes(10**5)

    DP = [0] * (10**5)
    for i in range(1,int(10**5)):
        DP[i] = DP[i-1]
        if is_prime(prime_list,i) and is_prime(prime_list,(i+1)//2):
            DP[i] += 1

    for l,r in zip(L,R):
        print(DP[r] - DP[l-1])

# 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:
from itertools import accumulate

# 入力
Q = int(input())
l, r = zip(*(map(int, input().split()) for _ in range(Q)))

# エラトステネスのふるいにより、素数表を作成する
is_prime = [i >= 2 for i in range(10**5 + 1)]
for i in range(2, 10**5 + 1):
    if is_prime[i]:
        for j in range(2 * i, 10**5 + 1, i):
            is_prime[j] = False

# i以下の2017に似た数の累積和を求める
dp = list(
    accumulate(
        range(10**5 + 1),
        lambda acc, i:
            acc + 1 if is_prime[i] and is_prime[(i + 1) // 2] else
            acc
    )
)

# 累積和を用いて各クエリに回答する
ans = '\n'.join(
    str(dp[b] - dp[a - 1])
    for a, b in zip(l, r)
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
Q=int(input())
n=100000
is_prime=[1]*(n+10)
is_prime[0]=0
is_prime[1]=0
for i in range(2,n+1):
	for j in range(i*2,n+1,i):
		if is_prime[j]==False:
			continue
		is_prime[j]=0
a=[0]*(n+10)
for j in range(2,n+1):
	if is_prime[j]%2==0:
		continue
	if is_prime[j] and is_prime[int((j+1)/2)]:
		a[j]=1
s=[0]*(n+10)		
for k in range(n):
	s[k+1]=a[k]+s[k]
ans=[]
for _ in range(Q):
	l,r=map(int,input().split())
	ans.append(s[r+1]-s[l])
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
def eratosthenes(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
                
    return prime_list

lr=[]
q=int(input())
p=0
for i in range(q):
    a=[int(j) for j in input().split()]
    lr.append(a)
    p=max(p,a[1])
ll=eratosthenes(p)
l=set(ll)
del ll[0]
li=[0 for i in range(p+2)]

for i in ll:
    if (i+1)//2 in l:
        li[i]+=1

from itertools import accumulate
la=list(accumulate(li))

for i in range(len(lr)):
    print(la[lr[i][1]]-la[lr[i][0]-1])

Submission status: Accepted

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

p_max = 101010
is_prime = [True] * (p_max)
is_prime[0] = is_prime[1] = False

for i in range(2, p_max):
    if not is_prime:
        continue
    for j in range(i+i, p_max, i):
        is_prime[j] = False

a = [0] * (p_max)
for i in range(p_max):
    if is_prime[i] is True and is_prime[(i+1)//2] is True:
        a[i] = 1

s = [0] * (p_max+1)
for i in range(p_max):
    s[i+1] = s[i] + a[i]

for i in lr:
    print(s[i[1]+1]-s[i[0]])

Submission status: Accepted

Solution code:
import bisect
Q = int(input())
lr = [[int(x) for x in input().split()]for _ in range(Q)]
li = [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]
for i in lr:
    begin = bisect.bisect_left(li,i[0])
    end = bisect.bisect_right(li,i[1])
    print(end-begin)

Submission status: Accepted

Solution code:
numq = int(input())
lis = [1]*100001
lis[0] = 0
lis[1] = 0
i = 2
while(i < 318):
  if lis[i] == 1:
    k = 2
    while(i*k < 100001):
      lis[i*k] = 0
      k += 1
  i += 1
lis2 = [0]*100001

for i in range(1,100001):
  if i % 2 == 1 and lis[i] == lis[(i+1)//2] == 1:
    lis2[i] = lis2[i-1] + 1
  else:
    lis2[i] = lis2[i-1]

for _ in range(numq):
  a,b = map(int,input().split())
  print(lis2[b] - lis2[a-1])

Submission status: Accepted

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

num = 10**5+10
Q = int(input())
prime_numbers = primes(num)
prime_set = set(prime_numbers)
prime_count = [0]*(num+1)
for pi in prime_numbers:
    if (pi+1)//2 in prime_set:
        prime_count[pi]+=1
for i in range(num):
    prime_count[i+1]+=prime_count[i]
for i in range(Q):
    l, r = map(int, input().split())
    print(prime_count[r]-prime_count[l-1])

Submission status: Accepted

Solution code:
import math
import sys
def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime
 
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
 
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
 
    return is_prime

input = sys.stdin.readline
N=10**5
prime=sieve(N)
a=[0 for i in range(N+1)]
for i in range(3,N+1):
	if prime[i] and prime[(i+1)//2]: a[i]=a[i-1]+1
	else: a[i]=a[i-1]

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

Submission status: Accepted

Solution code:
import math
import sys
def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime
 
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
 
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
 
    return is_prime

def main():
	N=10**5
	prime=sieve(N)
	a=[0 for i in range(N+1)]
	for i in range(3,N+1):
		if prime[i] and prime[(i+1)//2]: a[i]=a[i-1]+1
		else: a[i]=a[i-1]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime

    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False

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

    return is_prime


def main():
    input = sys.stdin.readline
    Q = int(input())
    is_prime = sieve(10**5)
    A = [0 for _ in range(10**5 + 1)]
    for i in range(3, 10**5 + 1):
        if is_prime[i] and is_prime[(i+1)//2]:
            A[i] = A[i-1] + 1
        else:
            A[i] = A[i-1]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime
 
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
 
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
 
    return is_prime

N=10**5
prime=sieve(N)
a=[0 for i in range(N+1)]
for i in range(3,N):
	if prime[i] and prime[(i+1)//2]: a[i]=a[i-1]+1
	else: a[i]=a[i-1]

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

Submission status: Accepted

Solution code:
import math
def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime
 
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
 
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
 
    return is_prime

N=10**5
prime=sieve(N)
a=[0]*(N)
for i in range(2,N):
	if prime[i] and prime[(i+1)//2]: a[i]=a[i-1]+1
	else: a[i]=a[i-1]

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

Submission status: Accepted

Solution code:
import math
def Sieve_of_Eratosthenes(N):
	prime={}
	for i in range(2,N+1):
		prime[i]=1

	for i in range(2,math.ceil(N**0.5)+1):
		tmp=set()
		for j in prime:
			if j>i and j%i==0: tmp.add(j)
		for j in tmp:
			prime.pop(j)

	return prime

N=10**5
prime=Sieve_of_Eratosthenes(N)
a=[0]*(N)
for i in range(2,N):
	if i in prime and (i+1)//2 in prime: a[i]=a[i-1]+1
	else: a[i]=a[i-1]

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

Submission status: Accepted

Solution code:
import math
def Sieve_of_Eratosthenes(N):
    prime=set(i for i in range(2,N+1))
    for i in range(2,math.ceil(N**0.5)+1):
        tmp=set()
        for j in prime:
            if j>i and j%i==0: tmp.add(j)
        for j in tmp:
            prime.remove(j)

    return(prime)

N=10**5+1
s=Sieve_of_Eratosthenes(N)
a=[0]*(N)
for i in range(2,N):
	if i in s and (i+1)//2 in s: a[i]=a[i-1]+1
	else: a[i]=a[i-1]

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

Submission status: Accepted

Solution code:
import math

def main():
    max_len = 10 ** 5 + 1
    sosuu_hantei = [0 for i in range(max_len)]

    for i in range(2, max_len):
        flg = 1
        for j in range(int(i ** 0.5) + 1):
            if sosuu_hantei[j]:
                if i % j == 0:
                    flg = 0
                    break
        if flg:
            sosuu_hantei[i] = 1

    # print(sosuu_hantei[:10])

    for i in range(max_len)[::-1]:
        if sosuu_hantei[i] == 0:
            continue
        if sosuu_hantei[(i + 1) // 2]:
            pass
        else:
            sosuu_hantei[i] = 0

    # print(sosuu_hantei[:10])

    now_count = 0
    for i in range(max_len):
        if sosuu_hantei[i]:
            now_count += 1
        sosuu_hantei[i] = now_count

    # print(sosuu_hantei[:10])

    num = int(input())
    for i in range(num):
        a, b = map(int, input().split())
        print(sosuu_hantei[b] - sosuu_hantei[a - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import math

def main():
    max_len = 10 ** 5 + 1
    sosuu_hantei = [0 for i in range(max_len)]

    for i in range(2, max_len):
        flg = 1
        for j in range(int(i ** 0.5) + 1):
            if sosuu_hantei[j]:
                if i % j == 0:
                    flg = 0
                    break
        if flg:
            sosuu_hantei[i] = 1

    # print(sosuu_hantei[:10])

    for i in range(max_len)[::-1]:
        if sosuu_hantei[i] == 0:
            continue
        if sosuu_hantei[(i + 1) // 2]:
            pass
        else:
            sosuu_hantei[i] = 0

    # print(sosuu_hantei[:10])

    now_count = 0
    for i in range(max_len):
        if sosuu_hantei[i]:
            now_count += 1
        sosuu_hantei[i] = now_count

    # print(sosuu_hantei[:10])

    num = int(input())
    for i in range(num):
        a, b = map(int, input().split())
        print(sosuu_hantei[b] - sosuu_hantei[a - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def sieve(n): # エラトステネスの篩
    num = [1]*n
    num[0]=num[1]= 0
    for i in range(int(n**0.5)+1):
        if num[i]:
            for j in range(i**2,n,i):
                num[j] = 0
    return num # list ### 1なら素数0なら合成数

primes = sieve(10**5)
like_2017 = [0]
for i in range(1,len(primes)):
    if i <= 2:
        like_2017.append(like_2017[i-1])
    elif primes[i] == 1 and primes[(i+1)//2] == 1:
        like_2017.append(like_2017[i-1]+1)
    else:
        like_2017.append(like_2017[i-1])
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(like_2017[r]-like_2017[l-1])

Submission status: Accepted

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

N = 10 ** 5 + 1
L = [1] * N

L[0] = 0
L[1] = 0

for i in range(2, N // 2):
  if L[i] == 1:
    for j in range(i * 2, N, i):
      L[j] = 0

S = [0] * N
for i in range(3, N, 2):
  S[i] = S[i - 2]
  if L[i] and L[(i + 1) // 2]:
    S[i] += 1

for l, r in lr:
  print(S[r] - S[max(l - 2, 1)])

Submission status: Accepted

Solution code:
prime = []
numberlist = []
for i in range(2, 317):
	numberlist.append(i)
while True:
	if numberlist[0] > 17:
		break
	p = numberlist.pop(0)
	newnumberlist = []
	while numberlist != []:
		now = numberlist.pop(0)
		if now%p != 0: newnumberlist.append(now)
	prime.append(p)
	numberlist = newnumberlist
for i in range(0, len(numberlist)):
	prime.append(numberlist[i])

def primejudge(n):
	if n == 1: return False
	if n in prime: return True
	for i in range(0, len(prime)):
		if n % prime[i] == 0: return False
	return True

like2017 = []
cnt = 0
for i in range(0, 100001):
	if i % 2 == 1:
		if primejudge(i) and primejudge((i+1)//2): cnt += 1
	like2017.append(cnt)

Q = int(input())
for i in range(0, Q):
	left, right = map(int, input().split())
	print(like2017[right]-like2017[left-1])

Submission status: Accepted

Solution code:
def sieve_of_eratosthenes(n):
    pl = [i for i in range(2, n + 1)]
    i=0
    p = pl[0]
    while p**2<=n:
        pl = [pl[j] for j in range(len(pl)) if pl[j]%p!=0 or j<=i]
        i+=1
        p=pl[i]
    return pl

pl=sieve_of_eratosthenes(100000)

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

for p in pl:
    if 2*p-1<=100000:
        p_list[2*p-1]+=1
    p_list[p]+=1


ps_list = [0]
ps = 0

for i in range(1,100001):
    if p_list[i]>=2:
        ps+=1
    ps_list.append(ps)



Q = int(input())

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

Submission status: Accepted

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

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def is_ok(n):
    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2):
        return True
    return False

def solve(Q: int, l: "List[int]", r: "List[int]"):
    N = 100000
    tmp = [0] * (N + 2)
    tmp[0] = 0
    tmp[1] = 0
    for i in range(1, N + 1):
        tmp[i + 1] = tmp[i]
        if is_ok(i):
            #print(i)
            tmp[i + 1] += 1
    #print(tmp[:10])
    for q in range(Q):
        ret = tmp[r[q] + 1] - tmp[l[q]]
        print(ret)
    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 math
import bisect
def makeprime(n):
  prime = []
  for i in range(2,n+1):
    flag = 1
    for j in range(2,math.ceil(math.sqrt(i)+1)):
       if not i == 2:
                   if i%j == 0:
                    flag = 0
                    break
    if flag:
     prime.append(i)
  return prime


def solve():
  q = int(input())
  primelike = []
  primenumber = makeprime(100001)
  for i in range(100001):
    if i%2 == 0:continue
    else:
      if i in primenumber:
        if (i+1)//2 in primenumber:
          primelike.append(i)
  for j in range(q):
      l,r = (int(k) for k in input().split())
      left = bisect.bisect_left(primelike,l)
      right = bisect.bisect_right(primelike,r)
      print(right-left)
solve()

Submission status: Accepted

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

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

L1=primes(100000)
L2=set(L1)
like2017=[]
for i in range(len(L1)):
  if (L1[i]+1)//2 in L2:like2017.append(L1[i])
like2017=set(like2017)
ansL=[]
ct=0
for i in range(100000):
  if i in like2017:ct+=1
  ansL.append(ct)

for i in range(q):
  print(ansL[l[i][1]]-ansL[l[i][0]-1])

Submission status: Accepted

Solution code:
import math

Q = int(input())
ls = []
rs = []

for i in range(Q):
    [l, r] = input().split() 
    ls.append(int(l))
    rs.append(int(r))

rmax = max(rs)

is_prime = [1]*(rmax+1)
is_prime[0] = 0
is_prime[1] = 0

i = 1

while i < math.sqrt(rmax):
    i += 1
    if is_prime[i] == 1:
        for j in range(i*2, rmax, i):
            is_prime[j] = 0

like2017 = [0]*(rmax+1)

for i in range(1, rmax+1, 2):
    if is_prime[i] == 1 and is_prime[int((i+1)/2)] == 1:
        like2017[i] = 1
        
cumul = [0]*(rmax+1)
for i in range(1, rmax+1):
    cumul[i] = cumul[i-1] + like2017[i]

for i in range(Q):
    print(cumul[rs[i]] - cumul[ls[i]-1])

Submission status: Accepted

Solution code:
Q=int(input())
SOSU={2}
from collections import defaultdict
data=dict()
data[-1]=0
data[0]=0
data[1]=0
data[2]=0
for i in range(3,10**5+1,2):
    data[i]=data[i-2]
    flag=True
    for j in range(3,int(i**0.5)+1):
        if i%j==0:
            flag=False
            break
    if flag:
        SOSU|={i}
        if (i+1)//2 in SOSU:
            data[i]+=1
for q in range(Q):
    l,r=map(int,input().split())
    print(data[r]-data[l-2])

Submission status: Accepted

Solution code:
q=int(input())
max=100001
is_prime =[1]*max
is_prime[0] = 0
is_prime[1] = 0
for i in range(2,max):
    if not is_prime[i]:
        continue
    for j in range(i*2,max,i):
        is_prime[j] = 0

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

s=[0]*(max+1)
for i in range(max):
    s[i+1]=s[i]+a[i]

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

Submission status: Accepted

Solution code:
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50

############
############
############

Q = i_inpl()
l, r = [], []

max_r = -INF
for _ in range(Q):
    li, ri = l_inpl()
    l.append(li)
    r.append(ri)
    max_r = max(max_r, ri)

MAX_X = 100030
prime_table = [True] * MAX_X
prime_table[0] = prime_table[1] = False

for (i, is_prime) in enumerate(prime_table):
    if is_prime:
        for n in range(i*i, MAX_X, i):
            prime_table[n] = False

# 1は2017に似てない数字
cumsums = [0]
for odd in range(3, max_r+3, 2):
    tmp = 0
    if prime_table[odd] and prime_table[(odd+1)//2]:
        tmp += 1
    cumsums.append(cumsums[-1] + tmp)

for li, ri in zip(l, r):
    if li > 1:
        li = li//2 - 1
    else:
        li = 0
    ri = ri//2
    print(cumsums[ri]-cumsums[li])

Submission status: Accepted

Solution code:
N = 100001
pr = [True]*(N+1)
c = [0]*(N+1)
pr[0] = pr[1] = False #exclude 0,1
for i in range(2,N) :
    if pr[i]:
        for j in range(i+i,N,i):#exclude mod i
            pr[j] = False

for i in range(3,N,2): # if L2017 -> c[i] +=1
    if pr[i] and pr[(i+1)//2]:
        c[i]+=1
for i in range(3,N):
    c[i]+=c[i-1]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(c[r]-c[l-1])

Submission status: Accepted

Solution code:
import copy
Q = int(input())
lis = []
maximam = 1
for _ in range(Q):
    l, r = map(int, input().split())
    lis.append((l, r))
    maximam = max(maximam, r)
flag_lis = [1] * (maximam+1)
flag_lis[0] = 0
flag_lis[1] = 0
for i in range(2, int((maximam-1)/2)+1):
    if flag_lis[i] != 0:
        for j in range(2*i,maximam+1,i):
            flag_lis[j] = 0
fin_lis = [0]*(maximam+1)
count = 0
for i in range(3, maximam+1, 2):
    if flag_lis[i] == 1 and flag_lis[int((i+1)/2)] == 1:
        count += 1
    fin_lis[i] = count
for (l, r) in lis:
    if l == 1:
        print(fin_lis[r] - 0)
    else:
        print(fin_lis[r] - fin_lis[l-2])

Submission status: Accepted

Solution code:
q = int(input())
l = [0]*(10**5+1)
p = set()
for i in range(2,10**5+1):
  if l[i] == 0:
    l[i] = 1
    p.add(i)
    for j in range(2*i,10**5+1,i):
      l[j] = -1
l = [0]*(10**5+1)
for x in p:
  if (x+1)//2 in p:
    l[x] = 1
for i in range(1,10**5+1):
  l[i] += l[i-1]
for _ in range(q):
  s,r = map(int, input().split())
  print(l[r]-l[s-1])