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:
q=int(input())
n =10**3
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
lists=[]
for i in prime:
    lists.append(i)  
lists=sorted(lists) 

checklist=[0]*(10**5+1)
checklist[0]=0
checklist[1]=0
count=0
for i in range(2,10**5+1):
    if i%2==0:
        checklist[i]=checklist[i-1]
    elif i%2!=0:
        if (all(i%j!=0 for j in lists) or i in lists) and (all(((i+1)//2)%j!=0 for j in lists) or (i+1)//2 in lists) :
            count+=1
            checklist[i]=checklist[i-1]+1
        else:
            checklist[i]=checklist[i-1]

listss=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    c=checklist[b]-checklist[a-1]
    listss[i]=c
for i in listss:
    print(i)

Submission status: Accepted

Solution code:
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 = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q = int(input())
rl = [map(int, input().split()) for _ in range(q)]

li = get_sieve_of_eratosthenes(10**5+1)
pli = [False] * (10**5+1)

for i in li:
  pli[i] = True

# print(pli)
  
# print(li)
cpli = [0] * (10**5+1)

cnt = 0
for i in range(10**5+1):
  if i % 2 == 1 and pli[i] and pli[(i + 1) // 2]:
    cnt += 1
  cpli[i] = cnt

# print(cpli)
  
for l, r in rl:
  print(cpli[r] - cpli[l-1])

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    pb = [True] * (10 ** 5 + 1)
    pb[0] = False
    pb[1] = False
    pl = [0] * (10 ** 5 + 1)
    pc = 0
    for i in range(2, len(pb)):
        if pb[i]:
            for j in range(i + i, len(pb), i):
                if pb[j]:
                    pb[j] = False
            if pb[(i + 1) // 2]:
                pc += 1
        pl[i] = pc
    n = int(input().rstrip('\n'))
    for i in range(n):
        l, r = list(map(int, input().rstrip('\n').split()))
        print(pl[r] - pl[l-1])


if __name__ == '__main__':
    slove()

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())
    
N = 10**5+1
prime = [1]*N
prime[0] = 0
prime[1] = 0
for i in range(2, N):
    if prime[i] == 1:
        j = 2*i
        while j < N:
            prime[j] = 0
            j += i

S = [0]*N
i = 3
temp = 0
while i < N:
    if i%2 == 1:
        if prime[i] == 1 and prime[(i+1)//2] == 1:
            temp += 1
    S[i] = temp
    i += 1
    
for i in range(Q):
    print(S[R[i]]-S[L[i]-1])

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline


# エラトステネスのふるい
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_list = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime_list + data
        prime_list.append(p)
        data = [e for e in data if e % p != 0]


prime = get_sieve_of_eratosthenes(10 ** 5)
p = set(prime)
prime = [i for i in prime if (i + 1) // 2 in p]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(bisect_right(prime, r) - bisect_left(prime, l))

Submission status: Accepted

Solution code:
from math import sqrt
# エラトステネスのふるい
def sieve(n):
  if n <2:
    return [False]*(n)
  is_prime = [True]*(n)
  is_prime[0], is_prime[1] = False, False
  for i in range(2, int(sqrt(MAX))):
    if is_prime[i]:
      for j in range(i*2, n, i):
        is_prime[j] = False
  return is_prime
    
# 2017-like 数かどうか
MAX = 10**5
is_prime = sieve(MAX)
a = [0]*(MAX)
for i in range(MAX):
  if i%2 == 0:
    continue
  if is_prime[i] 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]
  
# クエリ処理
Q = int(input())
for q in range(Q):
  l, r = map(int, input().split())
  print(s[r+1] - s[l])

Submission status: Accepted

Solution code:
q=int(input())
a=[0]*(10**5+1)
sosu=set()
sosu={i for i in range(2,10**5+1)}
for i in range(2,10**5+1):
	if i in sosu:
		for j in range(i*2,10**5+1,i):
			if j in sosu:
				sosu.remove(j)
cnt=0
for i in range(1,10**5,2):
	if i in sosu and (i+1)//2 in sosu:
		cnt+=1
	a[i]=cnt
	a[i+1]=cnt
for i in range(q):
	r,l=map(int,input().split())
	print(a[l]-a[r-1])

Submission status: Accepted

Solution code:
q = int(input())
n = 10**5
ansli = [0]*(n+1)

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 is_prime

li = primes(n+1)
for i in range(3,n + 1):
    if li[i] and li[(i+1)//2]:
        ansli[i] = ansli[i - 1] + 1
    else:
        ansli[i] = ansli[i - 1]

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

Submission status: Accepted

Solution code:
#Pはiが素数かどうかを表すlist
#素数でないと判明したらFalseに書き換える
P = [True]*100001
for i in range(2,100001):#2から始める
    if P[i]:
        for j in range(i+i,100000,i): #stepはi
            P[j] = False

#2017に似た数の個数をあらかじめ求める
#C[i]はi以下の2017に似た数の個数
C = [0 for _ in range(100002)]
#まずC[i]にiと(i+1)/2が2017likeであれば1を格納
for i in range(3,100000,2):
    if P[i] and P[(i+1)//2]:
        C[i] += 1
#C[i]はi<以下>の2017likeな数の個数なので，
#下から個数を足していく（累積和という）
for i in range(3,100000):
    C[i+1] += C[i]
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(C[r]-C[l-1])

Submission status: Accepted

Solution code:
import itertools
from itertools import accumulate

q=int(input())
x=[list(map(int, input().split())) for i in range(q)]
s=[0]*(1+10**5)
#素数のリスト
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

primes.sort()
for i in range(len(primes)):
    if primes[i]>5*10**4:
        break
    primes.append(2*primes[i])

primes.sort()
count=0
for i in range(len(primes)-1):
    if primes[i+1]-primes[i]==1 and primes[i+1]%2==0:
        s[primes[i]]=1
s=itertools.accumulate(s)
s=list(s)
a=0
b=0
for i in range(q):
    print(s[x[i][1]]-s[x[i][0]-1])

Submission status: Accepted

Solution code:
import numpy as np

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

range_max = 100000
tf = np.ones(range_max, dtype=int)
tf[0] = 0

i = 1
while True:
    if i == int(range_max ** (1 / 2)) + 1:
        break
    if not tf[i]:
        i += 1
        continue

    tmp = np.arange(i, range_max, i + 1)
    tf[tmp[1:]] = 0
    i += 1

counter = 0
counter_list = [0]
for i in range(2, 100000, 2):
    if tf[i] == 1 and tf[i//2] == 1:
        counter += 1
    counter_list.append(counter)

for i in range(q):
    left = lr[i][0]//2
    right = lr[i][1]//2
    res = counter_list[right] - counter_list[left]
    if left > 0 and counter_list[left] - counter_list[left-1] == 1:
        res += 1
    print(res)

Submission status: Accepted

Solution code:
S=[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]
C=[0]*(10**5+1)
for i in range(10**5+1):
  C[i]=C[i-1]
  if i in S:
    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 bisect
INFTY = 10**5
P = [1 for _ in range(INFTY)]
P[0]=0
P[1]=0
for i in range(2,int(INFTY**0.5)+1):
    for j in range(i*i,INFTY,i):
        P[j] = 0
Q = []
for i in range(INFTY):
    if P[i]==1:
        Q.append(i)
A = []
for q in Q:
    if P[(q+1)//2]==1:
        A.append(q)
B = {i:0 for i in range(1,INFTY,2)}

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

Submission status: Accepted

Solution code:
import sys
imput=sys.stdin.readline
import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
q=int(input())
x=[0]*q;y=[0]*q
for i in range(q):
    x[i],y[i]=map(int,input().split())
l=[]
for i in range(min(x),max(y)+1,2):
    d=prime_factorize(i)
    e=prime_factorize((i+1)//2)
    #print(d)
    if d==[i] and e==[(i+1)//2]:
        l.append(i)
#print(l)
for i in range(q):
    ans=0
    for j in range(len(l)):
        if x[i]<=l[j]<=y[i]:
            ans+=1
    print(ans)

Submission status: Accepted

Solution code:
n =10**5+1
p = [False] * 2 + [True] * (n-2)
for i in range(2,n):
    if p[i]:
        for j in range(i*2,n,i):
            p[j] = False
a=[p[i]==True and p[(i+1)//2]==True for i in range(n)]
b=[0]*n
b[0]=a[0]
for i in range(1,n):
    b[i]=b[i-1]+a[i]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(b[r]-b[l-1])

Submission status: Accepted

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

def eratosthenes_sieve(n: int):
    """
    エラトステネスの篩を用いてn以下の素数を求める
    """
    table = [0] * (n + 1)
    prime_list = [0, 0]
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(1)
            for j in range(i + i, n + 1, i):
                table[j] = 1
        else:
            prime_list.append(0)
    
    return prime_list

def solve(Q: int, l: "List[int]", r: "List[int]"):
    A = [0] * 100002
    prime_list = eratosthenes_sieve(100001)
    for i, p in enumerate(prime_list):
        if p == 1 and i % 2 == 1 and prime_list[(i+1)//2] == 1:
            A[i] = 1
        else:
            A[i] = 0
    A = list(itertools.accumulate(A))
    for q in range(Q):
        ll = l[q]
        rr = r[q]
        print(A[rr] - A[ll-1])
    return


# Generated by 1.1.5 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:
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
s=[0]*100007;s[2]=1
t=[0]*100007
for i in range(1,100001,2):s[i]+=is_prime(i)
for i in range(1,100001,2):t[i]=(s[i]+s[(i+1)//2])//2
for i in range(1,100007):t[i]+=t[i-1]
for i in range(int(input())):
	l,r=map(int,input().split())
	print(t[r]-t[l-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

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

qlen = ni()
q = [0] * (10**5 + 1)

pri = [0]* (10**5 + 1)
for num in range(1, 10**5):
    if is_prime(num):
        pri[num] = 1
for num in range(1, 10**5):
    if pri[(num + 1)//2] ==1 and pri[num] == 1:
        q[num] = q[num-1] + 1
    else:
        q[num] = q[num-1]

l, r = [], []
for i in range(qlen):
    li, ri = na()
    l.append(li)
    r.append(ri)
for li, ri in zip(l, r):
    print(q[ri]- q[li-1])

Submission status: Accepted

Solution code:
Q=int(input())
LR=[]
for i in range(Q):
    LR.append(list(map(int,input().split())))
L=[]
R=[]
for i in range(Q):
    L.append(LR[i][0])
    R.append(LR[i][1])

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

PL=primes(10**5)
LN=[]
for i in PL:
    if (i+1)//2 in PL:
        LN.append(i)

A=[0]*10**5
for i in LN:
    A[i]+=1

for i in range(1,10**5):
    A[i]+=A[i-1]
    
for i in range(Q):
    print(A[R[i]]-A[L[i]-1])

Submission status: Accepted

Solution code:
N = 100001
A,B = [True]*N,[0]*N
A[0],A[1] = False,False
for i in range(2,N):
    if A[i]:
        for j in range(i*2,N,i):
            A[j] = False
c=0
for i in range(3,N):
    if A[i] and A[(i+1)//2]:
        c += 1
    B[i] = c
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(B[r]-B[l-1])

Submission status: Accepted

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    import itertools
    def eratosthenes_sieve(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
        def inputs():return (int(x) for x in input().split())
    input = sys.stdin.readline
    def inputs():
        return (int(x) for x in input().split())
    M = 10**5
    prime_list=eratosthenes_sieve(M)
    kaku = set(prime_list)
    N = [0]*(M+1)
    for i in range(1,M+1,2):
        if i in kaku and ((i+1)/2 in kaku):
            N[i] =1 
    ans = list(accumulate(N))
    Q = int(input())
    for i in range(Q):
        l,r = inputs()
        print(ans[r]-ans[l-1])
main()

Submission status: Accepted

Solution code:
import math

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

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

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

primes = [0]
for i in range(1,10**5+3):
    if is_prime(i):
        primes.append(1)
    else:
        primes.append(0)

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

for lr in lrs:
    print(like20[lr[1]] - like20[lr[0]-1])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

prime_flags = [1]*(10**5+1)
prime_flags[1] = 0
for i in range(2, 10**5+1):
    if prime_flags[i] == 0:
        continue
    for j in range(2*i, 10**5+1, i):
        prime_flags[j] = 0

num2017s = []
for i in range(1, 10**5+1, 2):
    if prime_flags[i] == prime_flags[(i+1)//2] == 1:
        num2017s.append(i)

for l, r in LR:
    print(bisect_right(num2017s, r) - bisect_left(num2017s, l))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#素数判定
import math
def is_prime(n):
    if n == 1: return 0
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0
    return 1
  
Q = int(input())
#print(Q)
count_num = [0]*(10**5) #累積和

#print(count_num)

LR = []
l_min,r_max = float('inf'),0

for i in range(Q):
  l,r = map(int,input().split())
  l_min,r_max = min(l_min,l),max(r_max,r)
  LR.append([l,r])

 
count = 0
for i in range(l_min,r_max+1):
  if(i%2 == 1):
   if(is_prime(i) == 1):
    if(is_prime((i+1)//2) == 1): 
     count += 1
  count_num[i-1] = count


for i in range(Q):
  if(LR[i][0] == 1):
   ans = count_num[LR[i][1]-1]
  else:
   ans = count_num[LR[i][1]-1]-count_num[LR[i][0]-2] 
  print(ans)
#print(count_num)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7

#N = int(input())
#A = [int(x) for x in input().split()]
#V = [[0] * 100 for _ in range(100)]

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

def f(n):
    if n % 2 == 0:
        return False    
    if n in P and (n+1)//2 in P:
        return True
    return False


P = set(primes(10**5))

Q = int(input())
LR = []
for _ in range(Q):
    l,r = [int(x) for x in input().split()]
    LR.append((l,r))

A = []
cur = 0
for i in range(10 ** 5):
    if f(i):
        cur += 1
    A.append(cur)


for l,r in LR:
    print(A[r] - A[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]],is_prime
    
q = int(input())
Query = [list(map(int,input().split())) for _ in range(q)]

Primes,Is_Prime = primes(100000)

Like_2017 = [False]*(100000+1)
for p in Primes:
  if p*2-1 <= 100000 and Is_Prime[p*2-1]:
    Like_2017[p*2-1] = True

accum = 0
Accum = []
for i in range(100000+1):
  accum += int(Like_2017[i])
  Accum += [accum]

for query in Query:
  print(Accum[query[1]]-Accum[query[0]-1])

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
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]


if __name__ == '__main__':
    data = get_sieve_of_eratosthenes(100001)
    #print(data[:10])
    
    cnt=len(data)
    SS=[0]*(10**5+1)
    S=[0]*(10**5+1)
    T=[0]*(10**5+1)
    for d in data:
      SS[d]=1
    for i in range(3,len(S)):
      if SS[i] and SS[(i+1)//2]: S[i]=1
    for i in range(len(T)):
      T[i]=cnt
      cnt-=S[i]
    #print(T[:10])
    
    Q=int(input())
    for i in range(Q):
      l,r=map(int,input().split())
      print(T[l]-T[r]+S[r])

Submission status: Accepted

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

# 0以上整数x未満の素数のリストを返す(0,1は含まない)
import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0

    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 [prime for prime in primes if prime != 0]

def main():
    N = 10**5+1
    ps = primes(N)

    P = [0]*N
    for p in ps:
        P[p] = 1

    ruisekiwa = [0]*N
    for i in range(3, N, 2):
        if P[i] and P[(i+1)//2]:
            ruisekiwa[i] = 1
    for i in range(3, N):
        ruisekiwa[i] += ruisekiwa[i-1]
    
    Q = int(input())
    for _ in range(Q):
        l,r = map(int, input().split())
        ans = ruisekiwa[r] - ruisekiwa[l-1]
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def prime(n):
    is_prime=[True]*(n+1)
    is_prime[0],is_prime[1]=False,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]]

prime_number=prime(10**5)
number=[i for i in prime_number if (i+1)//2 in prime_number]+[0]
ans=[0]*(10**5+1)
count=0

for i in range(1,10**5):
    ans[i]=ans[i-1]
    if i==number[count]:
        ans[i] +=1
        count +=1

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

Submission status: Accepted

Solution code:
def prime(n):
    is_prime=[True]*(n+1)
    is_prime[0],is_prime[1]=False,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]]

prime_number=prime(10**5)
number=[i for i in prime_number if (i+1)//2 in prime_number]+[0]
ans=[0]*(10**5+1)
count=0
for i in range(1,10**5):
    ans[i]=ans[i-1]
    if i==number[count]:
        ans[i] +=1
        count +=1

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

Submission status: Accepted

Solution code:
"""def prime(n):
    is_prime=[True]*(n+1)
    is_prime[0],is_prime[1]=False,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]]

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

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