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())
que = []
for q in range(Q): que.append([int(i) for i in input().split()])

def Eratosthenes(n):
    li = [i for i in range(2,n+1)]
    judge = [True for i in range(n+1)]
    ans = []

    for i in range(2,n+1):
        if judge[i] == True:
            for j in range(i*2,n+1,i):
                judge[j] = False
            ans.append(i)
    judge[0],judge[1] = False,False
    return judge

judge = Eratosthenes(10**5)
tmp,ans = 0,[]
for i in range(10**5+1):
    if judge[i] == True and judge[int((i+1)/2)] == True: tmp+=1
    ans.append(tmp)

for q in que:
    l,r = q
    if l == r and judge[l]==True and judge[int((l+1)/2)] == True: print(1)
    else:
        tmp = ans[r]-ans[l]
        if (judge[l]==True and judge[int((l+1)/2)]==True) or (judge[r]==True and judge[int((r+1)/2)==True]):
            tmp += 1
        print(tmp)
    #print(ans[r],ans[l])

Submission status: Accepted

Solution code:
from math import sqrt, floor

num = 10**5

pnl = [False] * num
pnl[1:3] = [True] * 2
cln = [0] * (num + 1)

for i in range(3, num):
    if not i % 2:
        if pnl[i//2] and pnl[i-1]:
            cln[i-1] += 1
    else:
        sq = floor(sqrt(i))
        for j in range(3, sq+1, 2):
            if not i % j: break
        else: pnl[i] = True
    cln[i] = cln[i-1]

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

Submission status: Accepted

Solution code:
Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]
flg = [False] * (10**5+1)

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

def Eratosthenes(n):
    dp = [False]*n
    dp[0] = dp[1] = True
    prime = []
    for i in range(2,n):
        if dp[i]:
            continue
        prime.append(i)
        for j in range(i*2,n,i):
          dp[j] = True
    return prime

Era = Eratosthenes(10**5+1)
for e in Era:
  flg[e] = True

cnt = []
tmp = 0
for i in range(10**5+1):
  if flg[i] and flg[(i+1)//2]:
    tmp += 1
  cnt.append(tmp)

for i in range(Q):
  print(cnt[LR[i][1]] - cnt[LR[i][0]-1])

Submission status: Accepted

Solution code:
import math

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

# 試し割り法(2以外の偶数は捨てる方法を追加)
def check_prime(n):
    flag = True

    # n:evenかつ2でないならば素数でない
    # n=1は素数でない,n=0も実装しやすいように入れておく
    if (n % 2 == 0 and n != 2) or n == 0 or n == 1:
        flag = False
        return(flag)

    # n:oddまたは2のときは考える
    else:
        # 2からrootnまでに約数は存在しうる
        for i in range(2, math.floor(math.sqrt(n))+1):
            if n % i == 0:
                flag = False
                break
        return(flag)

MAX = 10**5 - 1
prime = [0]*((MAX+1)//2 + 1)
cnt = 0
for i in range(1, len(prime)):
    if check_prime(2*i - 1) and check_prime(i):
        cnt += 1
    prime[i] = cnt

for i in range(Q):
    left = (lr[i][0] - 1) // 2
    right = (lr[i][1] + 1) // 2
    ans = prime[right] - prime[left]
    print(ans)

Submission status: Accepted

Solution code:
def sieve_of_eratosthenes(N):
    prime_list = [True for _ in range(N + 1)]
    prime_list[0] = False
    prime_list[1] = False
    for p in range(2, int(N ** 0.5) + 1):
        if prime_list[p]:
            for i in range(2 * p, N + 1, p):
                prime_list[i] = False

    return prime_list


Q = int(input())
Max_ = 10**5
prime_list = sieve_of_eratosthenes(Max_)
count_list = [0]*(Max_+1)
count = 0
for i in range(Max_+1):
    if prime_list[i] and prime_list[(i + 1) // 2]:
        count += 1
    count_list[i] = count
for _ in range(Q):
    l, r = map(int, input().split())
    print(count_list[r] - count_list[l-1])

Submission status: Accepted

Solution code:
import math
import numpy as np

n = 10**5 + 1
p = [False] * n
c = [0] * n

def main():
    # 2からnまでの数字をsearch_listに入れる
    search_list = list(range(2,n))
    while True:
        # search_listの先頭の値が√nの値を超えたら処理終了
        if search_list[0] > math.sqrt(n):
            # search_listの残りの素数フラグを立てる
            for num in search_list:
                p[num] = True
            break
        else:
            # search_listの先頭の素数フラグを立てる
            tmp = search_list[0]
            p[tmp] = True
            # search_listの先頭をpopする
            search_list.pop(0)
            # search_listの先頭の倍数を取り除く
            search_list = [num for num in search_list if num % tmp != 0]

    # 1以上i以下のN-like数の数をc[i]とする
    for i in range(1,n):
        if p[i] and p[(i+1)//2]:
            c[i] = c[i-1] + 1
        else:
            c[i] = c[i-1]


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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                r[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    prime = Eratosthenes(10**5)
    prime_2017 = [False]*(10**5+1)
    for i in range(3,10**5+1,2):
        if prime[i]:
            prime_2017[i] = prime[(i+1)//2]

    cnt = [0]*(10**5+1)
    nxt = 0

    for i in range(1,10**5+1):
        if prime_2017[i]:
            nxt += 1
        cnt[i] = nxt

    Q = I()
    for _ in range(Q):
        l,r = LI()
        print(cnt[r] - cnt[l-1])

            


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from math import sqrt
from itertools import accumulate


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


def is_like_2017(x):
    if is_prime(x) and is_prime((x + 1) // 2):
        return True
    else:
        return False


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

nums = []
for i in range(1, 10 ** 5, 2):
    if is_like_2017(i):
        nums.append(1)
    else:
        nums.append(0)

acm = [0] + list(accumulate(nums))
for l, r in lr:
    ans = acm[(r+1)//2] - acm[(l+1)//2-1]
    print(ans)

Submission status: Accepted

Solution code:
def resolve():
    q = int(input())
    lr = list(list(map(int, input().split())) for _ in range(q))
    primes = sieve(10 ** 5)

    # accumulate
    acc = []
    now = 0
    for i in range(10 ** 5):
        if primes[i] and primes[(i + 1) // 2]:
            now += 1
        acc.append(now)

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


def sieve(n):
    is_prime = [True for _ in range(n + 1)]
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for i in range(2 * p, n + 1, p):
                is_prime[i] = False
    is_prime[0], is_prime[1] = False, False
    return is_prime


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# エラトステネスの篩, 累積和
from math import sqrt

N = 10 ** 5

p = [True] * (N + 1)
p[0] = False
p[1] = False
n = int(sqrt(N) + 1)
for j in range(4, N + 1, 2):
  p[j] = False
for i in range(3, n + 1, 2):
  if p[i]:
    for j in range(i + i, N + 1, i):
      p[j] = False

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

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

Submission status: Accepted

Solution code:
# エラトステネスの篩, 累積和
from math import sqrt

N = 10 ** 5

p = [True] * (N + 1)
p[0] = False
p[1] = False
n = int(sqrt(N) + 1)
for j in range(4, N + 1, 2):
  p[j] = False
for i in range(3, n + 1, 2):
  if p[i]:
    for j in range(i + i, N + 1, i):
      p[j] = False

c = [0] * (N + 1)
for i in range(3, N + 1, 2):
  if p[i] and p[(i + 1) // 2]:
    c[i] = 1
for i in range(1, N + 1):
  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:
# エラトステネスの篩, 累積和
from math import sqrt
p = [True] * (10 ** 5 + 1)
p[0] = False
p[1] = False
n = int(sqrt(10 ** 5)) + 1
for j in range(4, 10 ** 5 + 1, 2):
  p[j] = False
for i in range(3, n + 1, 2):
  if p[i]:
    for j in range(i + i, 10 ** 5 + 1, i):
      p[j] = False
c = [0] * (10 ** 5 + 2)
for i in range(2, 10 ** 5 + 2):
  c[i] = c[i - 1]
  if p[i - 2] and p[(i - 1) // 2]:
    c[i] += 1
q = int(input())
for _ in range(q):
  l, r = map(int, input().split())
  print(c[r + 2] - c[l + 1])

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


MAX = 10**5


def eratosthenes(n):
    is_prime = [1] * n
    is_prime[0] = 0

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = 0
                j += i
    return is_prime


def main():
    q = int(input())
    is_prime = eratosthenes(MAX)

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

    s = [0] + a
    s = list(accumulate(s))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ABC084D - 2017-like Number
from bisect import bisect_left as bsl, bisect_right as bsr


def get_primes(n: int) -> list:
    # return a list of primes <= n
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q, *LR = map(int, open(0).read().split())
    P = get_primes(10 ** 5 + 1)
    S = set(P)
    sel = [p for p in P if (p + 1) // 2 in S]  # 2017-like primes (selected P)
    # the number of 2017-like primes b/w l, r -> bisect[r] - bisect[l]
    ans = [bsr(sel, r) - bsl(sel, l) for l, r in zip(*[iter(LR)] * 2)]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC084D - 2017-like Number
from bisect import bisect_left as bsl, bisect_right as bsr


def get_primes(n: int) -> list:
    # return a list of primes <= n
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q, *LR = map(int, open(0).read().split())
    P = get_primes(10 ** 5 + 1)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]  # 2017-like primes
    # the number of 2017-like primes b/w l, r -> bisect[r] - bisect[l]
    ans = [bsr(selected_P, r) - bsl(selected_P, l) for l, r in zip(*[iter(LR)] * 2)]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
Q = int(input())
PN, i = [2] + [x for x in range(3, 10**5, 2)], 1
while PN[i] < (10**5) ** 0.5:
    x, j = PN[i], -1
    while PN[j] != x:
        if PN[j] % x == 0:
            PN.pop(j)
        j -= 1
    i += 1

PNf = [0, 1] + [0] * (10**5 // 2)
ans = [0, 1] + [0] * (10**5 // 2)
i, j, temp = 2, 2, 1
while i < len(PN):
    x = PN[i]
    while x != j * 2 + 1:
        ans[j] = temp
        j += 1
    PNf[j] = 1
    if j % 2 == 0 and PNf[j//2] == 1:
        temp += 1
    i += 1
    ans[j] = temp
    j += 1

ans = ans[:j] + [temp] * (10**5 // 2 - j)

for _ in range(Q):
    l, r = map(int, input().split())
    if l == 1:
        print(ans[r//2])
    else:
        print(ans[r//2] - ans[l//2 - 1])

Submission status: Accepted

Solution code:
def main():
    q = int(input())
    p_s = primes()
    is_like_2017 = is_like_2017_function(p_s)

    counter = 0

    memo = [0] * (10**5+1)

    for i in range(0, 10**5+1):
        if is_like_2017(i):
            counter += 1
        memo[i] = counter

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


def is_like_2017_function(primes):
    def _f(num):
        if primes[num] and primes[(num+1)//2]:
            return True
        else:
            False
    return _f


def primes():
    MAX = 10**5+1
    result = [True] * MAX
    result[0] = False
    loop_max = int(MAX**0.5) + 1
    for i in range(loop_max):
        if result[i]:
            for j in range((i+1)*2 - 1, MAX, (i+1)):
                if (j+1) % (i+1) == 0:
                    result[j] = False
    return [False] + result


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
q = int(input())

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 [int(i) for i in is_prime]

n = 10**5
p = primes(n)
s = [-1]*(n+1)
for i in range(n):
  if p[i]==1 and p[(i+1)//2]:
    s[i] = 1
  else:
    s[i] = 0

from itertools import accumulate
s = list(accumulate(s))
for i in range(q):
  l,r = (int(i) for i in input().split())
  print(s[r]-s[l-1])

Submission status: Accepted

Solution code:
prime = [True]*((10**5)+1)
prime[0]=False
prime[1]=False
for i in range(2,10**3):
  if i*i>10**5:
    break
  if prime[i]:
    for j in range(i,10**5):
      if i*j>10**5:
        break
      prime[i*j]=False

prime2017 = [x for x in prime]
prime2017[2] = False
for i in range(3,(10**5)+1):
  if prime[i]:
    prime2017[i] = prime[(i+1)//2]

count = 0
csum = [0]*((10**5)+1)
for i in range((10**5)+1):
  if prime2017[i]:
    count+=1
  csum[i]=count

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    c=10**5+1
    # S[i]: iがprimeかを指すboolean
    S=[1]*c
    S[0]=0; S[1]=0
    for i in range(2,c):
        if S[i]==0: continue
        for j in range(2*i,c,i):
            S[j]=0
    # T[i]: iが2017-like primeかを指すboolean
    T=[0]*c
    for i in range(3,c,2):
        if S[i] and S[(i+1)//2]:
            T[i]=1
    # cumsum
    for i in range(c-1):
        T[i+1]+=T[i]
    # input
    q=int(input())
    for _ in range(q):
        l,r=map(int,input().split())
        print(T[r]-T[l-1])
resolve()

Submission status: Accepted

Solution code:

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


def soinsu_bunkai(n):
	num = n
	i = 2
	sosu = 1
	while i <= n**0.5:
		if num % i == 0:
			sosu = 0
			break
		i += 1
	return sosu

sosu = [0 for _ in range(100000)]
sosu[2 - 1] = 1

for i in range(2, 100000, 2):
	sosu[i] = soinsu_bunkai(i + 1)

sosu2017 = [0 for _ in range(100000)]
for i in range(3, 100000, 2):
	if sosu[i - 1] == 1 and sosu[(i + 1)//2 - 1] == 1:
		sosu2017[i] = 1

ruiseki = [0]
for i in range(100000):
	ruiseki.append(ruiseki[-1] + sosu2017[i])

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

Submission status: Accepted

Solution code:
import math
Q = int(input())

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

table=[0]*100001
for i in range(1,100001):
  if i%2==1 and sosuu(int((i+1)/2)) and sosuu(i):
    table[i]=table[i-1] + 1
  else:
    table[i]=table[i-1]
#print(table[0:10])
ans=[0]*Q
for i in range(Q):
  l,r=map(int,input().split())
  ans[i]=table[r] - table[l-1]
  
for i in range(Q):
  print(ans[i])

Submission status: Accepted

Solution code:
import math
prime = [i for i in range(2, 10**5+1)]
for i in range(2, math.floor(math.sqrt(10**5))+1):
    prime = [p for p in prime if (p == i or p % i != 0)]
isPrime = [False for i in range(10**5+1)]
for p in prime:
    isPrime[p] = True
cntPrime = [0 for i in range(10**5+1)]
for i in range(2, 10**5+1):
    if i % 2 == 1 and isPrime[i] and isPrime[(i+1)//2]:
        cntPrime[i] = cntPrime[i-1]+1
    else:
        cntPrime[i] = cntPrime[i-1]

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

Submission status: Accepted

Solution code:
import bisect
import math

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

lis = []
for i in range(3, 100000, 2):
    if prime(i) and prime((i + 1) / 2):
        lis.append(i)

Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    left_ind = bisect.bisect_left(lis, l)
    right_ind = bisect.bisect_right(lis, r)
    print(right_ind - left_ind)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
q = int(input())

ls = [0]*q
rs = [0]*q

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

n = max(rs)
ass = []
is_prime = [True]*(n+1)
is_prime[0] = False
is_prime[1] = False

is_like = [0]*(n+1)
  
for i in range(2, n+1):
  if not is_prime[i]:
    continue
  if i%2 == 1 and is_prime[(i+1)//2] == True:
    is_like[i] = 1
  for j in range(i*2, n+1, i):
    is_prime[j] = False

from itertools import accumulate
cum_like = list(accumulate(is_like))

#print(cum_like)
for i in range(q):
  r = rs[i]
  l = ls[i]
  print(cum_like[r]-cum_like[l-1])

Submission status: Accepted

Solution code:
import itertools


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


sieve = eratosthenes(10**5)
ls = [False for _ in range(10**5)]
for n in range(3, 10**5, 2):
    ls[n] = sieve[n] and sieve[(n + 1) // 2]
accs = list(itertools.accumulate(map(int, ls)))

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

Submission status: Accepted

Solution code:
import numpy as np

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 main():
    q = int(input())
    ls = [[0,0] for _ in range(q)]
    for i in range(q):
        l,r = map(int,input().split())
        ls[i][0],ls[i][1] = l,r
    
    primes = seachPrimeNum(10**5)
    prime_ls1 = [0 for _ in range(10**5+1)]

    for prime in primes:
        prime_ls1[prime] =1


    prime_ls2 = [0 for _ in range(10**5+1)]

    for prime in primes:
        N = (prime+1)//2
        if prime_ls1[N]==1:
            prime_ls2[prime] = 1
        else:
            pass

    
    for i in range(1,10**5+1):
        prime_ls2[i] += prime_ls2[i-1]
    
    for i in range(q):
        l,r = ls[i]
        print(prime_ls2[r]-prime_ls2[l-1])    

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
# import numpy as np


# 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


# pn = np.array(seachPrimeNum(100002))
# pn2 = pn*2-1

# n2017 = sorted(list(set(pn) & set(pn2)))
n2017=[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]

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

Submission status: Accepted

Solution code:
def eratosutenes(n):
    primes = [1] * (n+1)  # 0からnまでの素数リスト, 最初は全てが素数だと仮定する
    primes[0] = 0
    primes[1] = 0

    for i in range(2, int(n**(1/2))+1):
        if primes[i] == 0:
            continue
        if primes[i] == 1:
            for j in range(i * 2, n+1, i):
                primes[j] = 0
    return primes


# 素数に1がたち、素数でないものに0がたつリストができた
primes = eratosutenes(100001)

Q = int(input())
query = []

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

like_numbers_ruisekiwa = [0]  # 0のときは0

for i in range(1, len(primes)):
    if i % 2 == 1:  # 奇数のときだけ処理をする
        if primes[i] == 1 and primes[(i+1)//2] == 1:  # 両方素数ならインクリメントする
            like_numbers_ruisekiwa.append(like_numbers_ruisekiwa[-1] + 1)
        else:
            like_numbers_ruisekiwa.append(like_numbers_ruisekiwa[-1])
    if i % 2 == 0:
        like_numbers_ruisekiwa.append(like_numbers_ruisekiwa[-1])


for i in range(len(query)):
    l, r = query[i]
    print(like_numbers_ruisekiwa[r] - like_numbers_ruisekiwa[l-1])

Submission status: Accepted

Solution code:
def p_prime(n): 
    prime = [2]
    for i in range(3,n+1):
        flag = 0
        for j in prime:
            if i%j == 0:
                flag = 1
                break
            if i**0.5 < j:
                break
        if flag == 0:
            prime.append(i)
    return prime

def main():
    import sys
    input = sys.stdin.readline
    
    Q = int(input())
    prime = p_prime(10**5)
    isprime = {}
    for i in prime:
        isprime[i] = 1
    A = [0]*(10**5+1)
    for i in range(1,10**5+1):
        if i in prime and (i+1)//2 in prime:
            A[i] = 1
    for i in range(1,10**5+1):
        A[i] += A[i-1]
    
    for i in range(Q):
        L,R = map(int,input().split())
        print(A[R]-A[L-1])
    
    
    
main()

Submission status: Accepted

Solution code:
q = int(input())
def isPrime(n) :
    if (n <= 1) :
        return False
    if (n <= 3) :
        return True

    if (n % 2 == 0 or n % 3 == 0) :
        return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

isprime = [False] * (10**5 + 1)
for i in range(1, 10**5+1):
    if isPrime(i):
        isprime[i] = True
ans = [0] * (10**5 + 1)
v = 0
for i in range(1, 10**5+1):
    if i % 2 == 1 and isprime[i] and isprime[(i+1)//2]:
        v += 1
    ans[i] = v
for i in range(q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l-1])

Submission status: Accepted

Solution code:
from math import sqrt, ceil

cache = {3}
primes = {2,3}
def isprime(n):
    if n in primes:
        return True
    for i in range(3, ceil(sqrt(n))+1, 2):
        if n % i == 0:
            return False
    primes.add(n)
    return True

def prepare():
    l = 5
    r = 10**5-1
    for n in range(l, r+1, 4):
        if n in cache:
            continue
        m = (n - 1) // 2
        if isprime(m+1) and isprime(n):
            cache.add(n)

def solve(l, r):
    cnt = 0
    if l <= 3 <= r:
        cnt = 1
        l = 5
    if l % 4 == 3:
        l += 2
    for n in range(l, r+1, 4):
        if n in cache:
            cnt += 1
            continue
        m = (n - 1) // 2
        assert n % 4 == 1
        if isprime(m+1) and isprime(n):
            cache.add(n)
            cnt += 1
    return cnt

def main():
    global cache
    from bisect import bisect_left, bisect_right
    cache = sorted(cache)
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        i = bisect_left(cache, l)
        j = bisect_right(cache, r)
        print(j-i)

prepare()
main()

Submission status: Accepted

Solution code:
import math
import bisect

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 = set(get_sieve_of_eratosthenes(100000))
    pos = []
    for i in data:
        if (i + 1) % 2 == 0:
            if (i + 1) // 2 in data:
                pos.append(i)
    pos.sort()
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        print(bisect.bisect_right(pos,r) - bisect.bisect_left(pos,l))

Submission status: Accepted

Solution code:
table_prime_numbers = [True for _ in range(10 ** 5)]
table_2017_numbers = [0 for _ in range(10 ** 5)]
table_2017_numbers_acm = [0 for _ in range(10 ** 5)]

def init_tables():
  table_prime_numbers[0] = table_prime_numbers[1] = False
  for i in range(2, 10 ** 5):
    if table_prime_numbers[i]:
      for j in range(i * 2, 10 ** 5, i):
        table_prime_numbers[j] = False
      if table_prime_numbers[(i + 1) // 2]:
        table_2017_numbers[i] = 1
  
  for i in range(2, 10 ** 5):
    table_2017_numbers_acm[i] = table_2017_numbers_acm[i - 1] + table_2017_numbers[i]
      
  return

def cumul(n):
  return table_2017_numbers_acm[n]

def result(l, r):
  return cumul(r) - cumul(l - 1)

def main():
  q = int(input())
  
  for _ in range(q):
    l, r = map(int, input().split())
    print(result(l, r))

  return

if __name__ == "__main__":
  init_tables()
  main()