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**5+10
d=[0]+[1 for _ in range(n)]

d[1]=0
f=2
while f*f<n+1:
  i=2
  while f*i<=n:
    d[f*i]=0
    i+=1
  f+=1
  while d[f]==0 and f*f<n+1:
    f+=1

e=[0 for _ in range(n+1)]
for i in range(1,n+1,2):
  if d[i]==1 and d[(i+1)//2]==1:
    e[i]=1

e[1]=0

import itertools
an=list(itertools.accumulate(e))

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

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

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

MAX=10**5
limit=int(math.sqrt(MAX))
primes=[2]
table=[i+1 for i in range(2,MAX,2)]
while limit>table[0]:
  primes.append(table[0])
  table=[j for j in table if j%table[0] != 0]
primes=set(primes+table)

similars=[0]*MAX
for i in range(2,MAX):
  if i in primes and (i+1)//2 in primes:
    similars[i]=1

similars=list(accumulate(similars))

for i in lr:
  l=i[0]
  r=i[1]
  print(similars[r]-similars[l-1])

Submission status: Accepted

Solution code:
import sys
def input():return sys.stdin.readline().strip()
from itertools import accumulate

def islike2017_list(n):
    primes = [True] * (n+1)
    primes[0] = False
    primes[1] = False

    # eratosthenes's sieve
    for i in range(2, int(n**0.5)+1):
        if not primes[i]:
            continue
        for j in range(i*2, n+1, i):
            primes[j] = False
    
    like2017 = [False] * (n+1)
    for i in range(n+1):
        if primes[i] and primes[(i+1)//2]:
            like2017[i] = True
    
    return like2017


def main():
    Q = int(input())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    MAX_X = 10**5
    like2017 = islike2017_list(MAX_X)
    CUSUM = tuple(accumulate(like2017))

    ans = [CUSUM[r] - CUSUM[l-1] for l, r in queries]
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from bisect import bisect_left, bisect_right


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


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


sosu = seachPrimeNum(10**5)[1:]
like_2017 = [i for i in sosu if is_prime((i+1) / 2)]

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    l_ix = bisect_left(like_2017, l)
    r_ix = bisect_right(like_2017, r)
    print(r_ix - l_ix)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc084/tasks/abc084_d
from itertools import accumulate


def get_prime(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        return []
    if n == 2:
        return [2]
    prime = [2]
    limit = int(n ** 0.5)
    nums = [i + 1 for i in range(2, n, 2)]
    while True:
        p = nums[0]
        if limit < p:
            return prime + nums
        prime.append(p)
        nums = [e for e in nums if e % p != 0]


primes = set(get_prime(10 ** 5))
like = [0] * 10 ** 5
for i in range(3, 10**5):
    if i in primes and (i + 1) // 2 in primes:
        like[i] = 1

like_accum = list(accumulate(like))

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

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
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(3,n + 1) if is_prime[i]]

prime = primes(10**5)
p_set = set(prime)
like = [3]
for i in prime:
    if (i+1)//2 in p_set:
        like.append(i)

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

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
import random
def is_prime(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
 
    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

prime = []
like = [3]
for i in range(3, 10**5+1):
    if is_prime(i):
        prime.append(i)
p_set = set(prime)
for i in prime:
    if (i+1)//2 in p_set:
        like.append(i)

Q = int(input())

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

Submission status: Accepted

Solution code:
Q = int(input())

minl = 10**9
maxr = -1
ans_range = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans_range.append((l, r))

    if l < minl:
        minl = l
    if r > maxr:
        maxr = r

dp = [0] * ((maxr - minl) + 2)

import math
for u in range(minl, maxr+1,1):
    check = (u + 1) / 2

    if not float.is_integer(check) or check == 1:
        dp[u - minl + 1] = dp[u-minl]
        continue

    ok = True
    for y in range(2, int(math.sqrt(check))+1):
        if check % y == 0:
            ok = False
            break

    ok2 = True
    for z in range(2, int(math.sqrt(u))+1):
        if u % z == 0:
            ok2 = False
            break
    
    if ok and ok2:
        # print("found: ", u)
        dp[u - minl + 1] = dp[u-minl] + 1
    else:
        # print("u:", u)
        dp[u - minl + 1] = dp[u-minl]

# print(dp)
for ll, rr in ans_range:
    if ll == rr:
        ans = dp[rr-minl+1] - dp[rr-minl]
    else:
        ans = dp[rr-minl+1] - dp[ll-minl]
    print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
b[c:] = add 
b[0::2] = 0

for i in range(n):
    l, r =map(int,input().split())
    print(b[r] - b[max(0, l - 2)] )

Submission status: Accepted

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
l = []
r = []
for i in range(n):
    l_, r_ =map(int,input().split())
    l.append(l_)
    r.append(r_)
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
b[c:] = add 
b[0::2] = 0
for i in range(n):
    e = b[max(0, l[i] - 2)]
    f = b[r[i]]
    print(f - e)

Submission status: Accepted

Solution code:
q = int(input())
l, r = [0] * q, [0] * q
for i in range(q):
    l[i], r[i] = map(int, input().split())
 
mini = min(min(l), min(r))
maxi = max(max(l), max(r))
ans = [0] * (maxi + 1)
prime = [0] * (maxi + 1)
def judge_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    
    return True if n != 1 else False
 
for i in range((mini + 1) // 2, maxi + 1):
    prime[i] = judge_prime(i)
 
for i in range(mini, maxi + 1, 2):
    ans[i] = ans[i - 2] + 1 if prime[i] and prime[(i + 1) // 2] else ans[i - 2]
for i in range(q):
    print(ans[r[i]] - ans[max(0, l[i] - 2)])

Submission status: Accepted

Solution code:
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
mr=0
for l,r in lr:
  mr=max(mr,r)
l=[1 for _ in range(mr+1)]
l[0],l[1]=0,0
s=[0 for _ in range(mr+1)]
for i in range(2,int(mr**(1/2))+1):
  x=i*2
  while x<=mr:
    l[x]=0
    x+=i
for i in range(2,mr+1):
  if l[i]==1 and l[(i+1)//2]==1:
    s[i]=s[i-1]+1
  else:
    s[i]=s[i-1]
for l,r in lr:
  print(s[r]-s[l-1])

Submission status: Accepted

Solution code:
n = int(input())

def sieve_of_eratosthenes(n):
    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]

prime = sieve_of_eratosthenes(10**5 + 1)

numlike2017 = [0 for i in range(10**5 + 1)]
for i in prime:
    if (i+1)//2 in prime:
        numlike2017[i] = 1

def cumulative_sum(collection):
    result = [collection.pop(0)]
    for item in collection:
        result.append(result[-1] + item)
    return result
cs2017 = cumulative_sum(numlike2017)

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

for i in ans:
    print(i , flush=True)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    """
    エラトステネスの篩。√N以下の数に対して2から順にその数の倍数を消していく。
    計算量は「調和級数」になるのがミソ。具体的には
        N/2 + N/3 + N/5 + ... + N/(√N) = N * (1/2 + 1/3 + 1/5 + ... + 1/√N)
                                       = N * loglog(√N) (素数の逆数和の発散スピードがこれ)
                                       = N(loglogN - log2)
    """
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        return []
    prime = [1] * (n + 1)
    prime[0] = prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not prime[i]: continue
        for j in range(i * 2, n + 1, i):
            prime[j] = 0
    return prime


def main():
    primes = get_sieve_of_eratosthenes(100000)
    like = [0] * 10**5
    for i in range(3, 10**5):
        if primes[i] and primes[(i + 1) // 2]:
            like[i] = 1
    like = list(accumulate(like))

    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        if l < 3: l = 3
        if r < 3:
            print(0)
            continue
        print(like[r] - like[l - 1])



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_cumulative(A):
    C = [0] * (len(A) + 1)
    for i, a in enumerate(A):
        i += 1
        C[i] = C[i - 1] + a
    return C


def main():
    Q = NI()
    querys = [NLI() for _ in range(Q)]
    N = 100010
    hurui = [1] * N
    for i in range(N):
        if i <= 1:
            hurui[i] = 0
            continue
        if hurui[i] == 0:
            continue
        for j in range(i*2, N, i):
            hurui[j] = 0
    like_2017 = hurui[:]
    for i in range(N):
        if hurui[i] == 0 or i <= 2:
            continue
        if hurui[(i+1)//2] == 0:
            like_2017[i] = 0
    like_2017[2] = 0
    C = make_cumulative(like_2017)[1:]

    for q in querys:
        print(C[q[1]] - C[q[0]-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    """
    エラトステネスの篩。√N以下の数に対して2から順にその数の倍数を消していく。
    計算量は「調和級数」になるのがミソ。具体的には
        N/2 + N/3 + N/5 + ... + N/(√N) = N * (1/2 + 1/3 + 1/5 + ... + 1/√N)
                                       = N * loglog(√N) (素数の逆数和の発散スピードがこれ)
                                       = N(loglogN - log2)
    """
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        return []
    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]


def main():
    primes = get_sieve_of_eratosthenes(100000)
    like = [0] * 10**5
    for i in range(3, 10**5):
        if i in primes and (i + 1) // 2 in primes:
            like[i] = 1
    like = list(accumulate(like))

    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        if l < 3: l = 3
        if r < 3:
            print(0)
            continue
        print(like[r] - like[l - 1])



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    MAX_NUM = 10 ** 5
    Q = int(input())
    lr = [None] * Q
    for i in range(Q):
        lr[i] = tuple(map(int, input().split()))

    is_prime = [True] * (MAX_NUM + 1)
    is_prime[0] = False
    for i in range(4, MAX_NUM + 1, 2):
        is_prime[i] = False

    is_prime[1] = False
    for i in range(3, MAX_NUM + 1, 2):
        for j in range(3 * i, MAX_NUM + 1, 2 * i):
            is_prime[j] = False

    S = {}
    S[-1] = 0
    for i in range(1, MAX_NUM + 1, 2):
        if is_prime[i] and is_prime[(i + 1) // 2]:
            S[i] = S[i - 2] + 1
        else:
            S[i] = S[i - 2]

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
q=int(input())

primes=[True]*100001
primes[0]=False
primes[1]=False

for i in range(2,100001):
    if primes[i]:
        for j in range(2,100000//i+1):primes[i*j]=False

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

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

Submission status: Accepted

Solution code:
from math import sqrt
def sieve(n):
    if n <= 4:
        return list(range(2, n))
    def _sieve_of_eratosthenes(n):
        limit = int(sqrt(n))+1
        table = [1] * n
        table[0] = table[1] = 0
        for i in range(2, limit):
            if table[i]:
                for j in range(i**2, n, i):
                    table[j] = 0
        return [i for i in range(2, n) if table[i]]
    return _sieve_of_eratosthenes(n)

q, *LR = map(int, open(0).read().split())
P = set(sieve(10**5))
d = {-1:0}
s = 0
for i in range(1, 10**5, 2):
    s += i in P and (i+1)//2 in P
    d[i] = s
for l, r in zip(LR[::2], LR[1::2]):
    print(d[r] - d[l-2])

Submission status: Accepted

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

mini = min(min(l), min(r))
maxi = max(max(l), max(r))
ans = [0] * (maxi + 1)
prime = [0] * (maxi + 1)
def judge_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    
    return True if n != 1 else False

for i in range((mini + 1) // 2, maxi + 1):
    prime[i] = judge_prime(i)

for i in range(mini, maxi + 1, 2):
    ans[i] = ans[i - 2] + 1 if prime[i] and prime[(i + 1) // 2] else ans[i - 2]
for i in range(q):
    print(ans[r[i]] - ans[max(0, l[i] - 2)])

Submission status: Accepted

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

from itertools import accumulate
import sys
input = sys.stdin.readline

MAX = 100_000
primes = set(get_primes(MAX))
like = [0]*MAX
for n in range(MAX):
    if n in primes and (n+1)//2 in primes:
        like[n] = 1
like = list(accumulate(like))

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

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

q = ii()
rmax = 0
qer = []
for i in range(q):
    l,r = mi()
    qer.append([l,r])
    if rmax < r:
        rmax = r

# rmaxまで計算
# 奇数かつ4n-1ではない
# 4n+1

# 素数表
import math
primeList = [2,3,5,7,11,13]
for i in range(17,rmax+1,2):
    for j in primeList:
        if j > math.sqrt(i):
            primeList.append(i)
            break
        if i % j == 0:
            break

# print(primeList)
        
def checksim(x,pl):
    if x in pl and (x+1)//2 in pl:
        return 1
    return 0

tans = [0] * (rmax+1)
tans[3] = 1
for i in range(5,rmax+1,4):
    if checksim(i, primeList):
        tans[i] = 1

# cumsum
ans = [0]*(rmax+1)
tcumsum = 0
for i in range(rmax+1):
    if tans[i] == 1:
        tcumsum += 1
    ans[i] = tcumsum

for i in qer:
    print(ans[i[1]] - ans[i[0]-1])

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

a = [1]*(10**5+1)
a[0] = a[1] = a[2] = 0

for i in range(2, ceil(sqrt(10**5)+1)):
    for j in range(i*2, len(a), i):
        a[j] = 0
        if j*2 - 1 < len(a):
            a[j*2-1] = 0

q = INT()
p = [LIST() for i in range(q)]
s = list(accumulate(a))

for i in range(q):
    print(s[p[i][1]]-s[p[i][0]-1])

Submission status: Accepted

Solution code:
B = [False]*100005
C = [0]*100005
for i in range(2,100001):
    if not B[i]:
      	for j in range(i+i,100001,i):
          	B[j]=True
for i in range(3,100001,2):
    if not B[i] and not B[(i+1)//2]:
        C[i]+=1
for i in range(3,100001):
    C[i]=C[i]+C[i-1]
    
N = int(input())
for _ in range(N):
    a, b = map(int,input().split())
    print(C[b]-C[a-1])

Submission status: Accepted

Solution code:
q=int(input())
n=10**5

work=[1 if i%2==1 else 0 for i in range(n+1)]
primes=[2]
lst=[0]*(n+1)
work[1]==0

for i in range(3,n,2):
    if not work[i]: continue
    primes.append(i)
    index=1
    while i*index<=n:
        work[i*index]=0
        index+=1

for i in primes[1:]:
    if (i+1)//2 in primes:
        lst[i]=1

for i in range(3,n+1):
    lst[i]+=lst[i-1]

for _ in range(q):
    left,right=map(int,input().split())
    print(lst[right]-lst[left-1])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



q = int(input())
lr = [None]*q
for i in range(q):
    lr[i] = tuple(map(int, input().split()))
n = max(item[1] for item in lr) + 10

def hurui(n):
    """n以下の素数のリストを返す
    """
    l = list(range(2,n+1))
    p = 2
    i = 0
    while True:
        l = [item for item in l if item==p or item%p!=0]
        i += 1
        p = l[i]
        if p*p>n:
            break
    return l
l = hurui(n)
l = set(l)
v = [0]*n # 0, 1, ..., iのうちの個数
c = 0
for i in range(n):
    if i%2==1 and i in l and (i+1)//2 in l:
        c += 1
    v[i] = c
ans = []
for l,r in lr:
    ans.append(v[r]-v[l-1])
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
def generate_is_prime_sieve(N):
	is_prime = [True]*(N+1)
	is_prime[0] = is_prime[1] = False
	for p in range(2,N+1):
		if is_prime[p]:
			for n in range(2*p,N+1,p):
				is_prime[n] = False
	dummy=[x for x in is_prime]
	for p in range(2,N+1):
		if is_prime[p] and is_prime[(p+1)//2]:
			dummy[p]=True
		else:
			dummy[p]=False
	return dummy
def partial_sums(N):
	something=generate_is_prime_sieve(N)
	counter=0
	partial_sum=[0]*(N+1)
	for i in range(N+1):
		if something[i]:
			counter+=1
		partial_sum[i]=counter
	return partial_sum	
N=partial_sums(10**5+1)
for i in range(int(input())):
	counter=0
	a,b=[int(x) for x in input().split()]
	print(N[b]-N[a-1])

Submission status: Accepted

Solution code:
import math

q = int(input())

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

s = [0 for i in range(0,100001)]
for i in range(3,100001,2):
    if is_prime(i) and is_prime((i+1)//2):
        s[i] = 1

s2 = [0 for i in range(0,100001)]
tmp = 0
for i in range(100001):
    tmp += s[i]
    s2[i] = tmp

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    # np.set_printoptions(threshold=np.inf)
    N = pow(10, 5)
    is_prime = np.ones(N, dtype=bool)
    is_prime[:2] = False
    max = int(np.sqrt(N))
    for j in range(2, max + 1):
        if (is_prime[j]):
            is_prime[j*j::j] = False
    like_2017 = np.ones(N, dtype=bool)
    like_2017[:2] = False
    for i in range(2, N):
        if (i % 2 == 0):
            like_2017[i] = False
            continue
        if (not is_prime[i]):
            like_2017[i] = False
            continue
        if (not is_prime[(i + 1) // 2]):
            like_2017[i] = False
            continue

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


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:
like2017numbers = {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}
N = 10**5
dp_table = [0]*(N+1)
for i in range(N):
    if i+1 in like2017numbers:
        dp_table[i+1] = dp_table[i]+1
    else:
        dp_table[i+1] = dp_table[i]

def solve():
    Q = int(input())
    for _ in range(Q):
        l,r = map(int, input().split())
        # print(dp_table[l-1], dp_table[r])
        print(dp_table[r]-dp_table[l-1], flush=True)
        
solve()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

lim = 10**5

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

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

dp = [0]*(lim+1)
for i in range(lim+1):
	if is_prime[i] and is_prime[(i+1)//2]:
		dp[i] = 1

dp = list(accumulate(dp))

Q = INT()
for _ in range(Q):
	l, r = MAP()
	print(dp[r]-dp[l-1])

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(100000,-1,-1):
    if prime[i]:
        if prime[(i+1)//2] != 1:
            prime[i] = 0

from itertools import accumulate
accum = list(accumulate(prime))

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