Problem:


Score : 400 points

Problem Statement

We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Sample Input 1

1
3 7

Sample Output 1

2

3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.

5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.

7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.

Thus, the response to the first query should be 2.

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

6
1 53
13 91
37 55
19 51
73 91
13 49

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Accepted

Solution code:
import math 

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

#エラトステネスのふるい
MAX =100000
is_prime = [1]*(MAX+1)
is_prime[0] = 0 
is_prime[1] = 0
for i in range(2,MAX+1):
    if prime(i) == 1:
        j = i*2
        while j <= MAX:
            is_prime[j] = 0
            j += i

#２０１７のような数かどうか
a = [0]*(MAX+1)
for i in range(0,MAX):
    if i % 2 == 1:
        if is_prime[i]==1 and is_prime[int((i+1)/2)]==1:
            a[i] = 1

#累積和
s = [0] * (MAX+1)
for i in range(0,MAX):
    s[i+1] = s[i] + a[i]

#クエリ処理
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    r += 1

    print(s[r]-s[l])

Submission status: Accepted

Solution code:
from itertools import accumulate
Q = int(input())
ans = []
def eratosthenes(N):
    searchList = [i for i in range(2,N)]
    primeNum = []


    mx = int(N**0.5+1)
    while searchList[0] <= mx:
        primeNum.append(searchList[0])
        tmp = searchList[0]
        searchList = [i for i in searchList if i%tmp != 0]
    primeNum.extend(searchList)
    return primeNum

ok = [0]*(10**5+1)
primeNum = eratosthenes(10**5+1)
primeNumLst = [False] * (10**5+1)

for p in primeNum:
    primeNumLst[p] = True

for p in primeNum:
    if primeNumLst[(p+1)//2]:
        ok[p] = 1
    
ok = list(accumulate(ok))

for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(ok[r] - ok[l-1])
    
print("\n".join(map(str,ans)))

Submission status: Accepted

Solution code:
import math
def isprime(n):
    if n==1:return(False)
    if n==2:return(True)
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:return(False)
    return(True)
s=set([i for i in range(1,10**5,4) if isprime(i) and isprime((i+1)//2)])
s.add(3)
l=[i in s for i in range(10**5)]
ls=[]
tmp=0
for i in l:
    tmp+=i
    ls.append(tmp)
n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    print(ls[r]-ls[l-1])

Submission status: Accepted

Solution code:
def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return p


p, c = primes(10 ** 5), [0]
for i in range(1, 10 ** 5 + 1):
    c.append(c[-1] + 1 if p[i] and p[(i + 1) // 2] else c[-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:
def primes(N):
    '''Sieve of Eratosthenes'''
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return p


p, c = primes(10 ** 5), [0]
for i in range(1, 10 ** 5 + 1):
    c.append(c[-1] + 1 if p[i] and p[(i + 1) // 2] else c[-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 math
from bisect import bisect_left, bisect_right

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

is_prime = [False for _ in range(100001)]
is_prime[3] = True
primes = [3]
for n in range(5, 100001, 2):
    prime = True
    i = 2
    while i < int(math.sqrt(n)) + 1:
        if n % i == 0:
            prime = False
            break
        i += 1
    if prime:
        primes.append(n)
        is_prime[n] = True

like = []
for p in primes:
    if p == 3:
        like.append(p)
        continue
    q = (p+1)//2
    if is_prime[q]:
        like.append(p)

for l, r in LR:
    ans = bisect_right(like, r) - bisect_left(like, l)
    print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

Q = int(input())
LR = [None]*Q
maxr = 0
for i in range(Q):
    l, r = map(int, input().split())
    LR[i] = (l, r)
    maxr = max(maxr, r)

primes = set(range(2, maxr + 1))
for i in range(2, int(maxr ** 0.5 + 1)):
    primes.difference_update(range(i * 2, maxr + 1, i))
c = [0]*((maxr+1) // 2)
for p in primes:
    if p <= (maxr + 1) // 2:
        c[p - 1] = 1
likes = [0]*maxr
for p in primes:
    if p != 2 and c[(p+1) // 2 - 1] == 1:
        likes[p-1] = 1
likes = list(accumulate(likes))
for i in range(Q):
    if LR[i][0] == 1:
        print(likes[LR[i][1] - 1])
    else:
        print(likes[LR[i][1] - 1] - likes[LR[i][0] - 2])

Submission status: Accepted

Solution code:
class erat():
    def __init__(self,n):
        self.d = set()
        self.prime = set()
        for i in range(2,n+1):
            ind = 2
            if i not in self.d:
                self.prime.add(i)
            while(True):
                temp = i*ind
                ind += 1
                if temp > n:
                    break
                else:
                    if temp not in self.d:
                        self.d.add(temp)
    def isprime(self,n):
        if n in self.prime:
            return True
        else:
            return False

e = erat(10**5)
arr = [0 for i in range(10**5+1)]
for i in range(3,10**5+1):
    if e.isprime(i) and e.isprime((i+1)//2):
        arr[i] = arr[i-1]+1
    else:
        arr[i] = arr[i-1]
# print(arr[:10])
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(arr[r]-arr[l-1])

Submission status: Accepted

Solution code:
def Eratosthenes(n):
    prime_list = [True for _ in range(n + 1)]
    prime_list[0] = False
    prime_list[1] = False
    for j in range(4, n + 1, 2):
        prime_list[j] = False
    prime_list[2] = True
    for i in range(3, int(n ** 0.5) + 1, 2):
        if prime_list[i]:
            for j in range(i * 2, n + 1, i):
                prime_list[j] = False
    return prime_list


def prime_2017(prime_list):
    prime_2017_list = [True for _ in range(len(prime_list))]
    for i in range(len(prime_list)):
        if i <= 2:
            prime_2017_list[i] = False
        elif prime_list[i]:
            if not prime_list[(i + 1) // 2]:
                prime_2017_list[i] = False
        else:
            prime_2017_list[i] = False
    return prime_2017_list

q = int(input())
num_list = []
num_max = 0
for _ in range(q):
    l, r = map(int, input().split())
    num_list.append([l, r])
    num_max = max(r, num_max)
prime_list = Eratosthenes(num_max)
prime_2017_list = prime_2017(prime_list)
prime_num = [0 for _ in range(num_max + 1)]
for i in range(num_max):
    prime_num[i + 1] = prime_num[i] + prime_2017_list[i + 1]

for l, r in num_list:
    print(prime_num[r] - prime_num[l - 1])

Submission status: Accepted

Solution code:
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        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]]

Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
 
K = max(r)
prime = prime(K)
a = [1]*(K+1)
s = [0]*(K+1)
a[0] = 0
a[1] = 0
for i in range(2,K+1):
    if a[i]:
        for j in range(i*i, K+1, i):
            a[j] = 0

for i in range(3,K+1,2):
    if a[i] and a[(i+1)//2]:
        s[i] = 1

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

for i in range(Q):
    rr, ll = r[i], l[i]
    if rr == ll:
        if s[ll]-s[ll-2] == 1:
            print(1)
        else:
            print(0)
    else:
        print(s[rr] - s[ll-1])

Submission status: Accepted

Solution code:
def get_isPrime(n):         #1~nまでの数で、素数は1、それ以外は0となるようなリストを返す
    isprime=[1]*(n+1)
    isprime[0]=0
    isprime[1]=0
    for i in range(2, int(n**0.5)+1):
        if not isprime[i]:
            continue
        for j in range(i*2, n+1, i):
            isprime[j]=0
    return isprime

max_n=100000
isprime=get_isPrime(max_n)

ruiseki=[]
for i in range(max_n+1):
    if i==0 or i==1 or i==2:
        ruiseki.append(0)
    else:
        if i%2==0:
            ruiseki.append(ruiseki[i-1])
        else:
            if isprime[i] and isprime[int((i+1)/2)]:
                ruiseki.append(ruiseki[i-1]+1)
            else:
                ruiseki.append(ruiseki[i-1])

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

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect
ref=deque([2])
refref=deque()
for i in range(3,100000,2):
	flag=1
	for j in range(2,int(i**0.5)+1):
		if i%j==0:
			flag=0
			break
	if flag:
		ref.append(i)
for p in ref:
	if (p+1)//2 in ref:
		refref.append(p)
q,*li=map(int,open(0).read().split())
for l,r in zip(li[::2],li[1::2]):
	print(bisect(refref,r+1)-bisect(refref,l-1))

Submission status: Accepted

Solution code:
count = int(input())
params = []

for i in range(count):
    params.append(tuple(map(int, input().split())))

maxNum = max(params, key= lambda n : n[1])

sosuList = [1] * (maxNum[1] + 1)
sosuList[0] = 0
sosuList[1] = 0

for i in range(2, len(sosuList)):
    if sosuList[i] == 1:
        for j in range(i + i, len(sosuList), i):
            sosuList[j] = 0

ruisekiwaList = [0] * (len(sosuList) + 1)

for i in range(2, len(sosuList)):
    ruisekiwaList[i + 1] = ruisekiwaList[i] 
    if sosuList[i] == 1 and sosuList[int((i + 1) /2)] == 1:
        ruisekiwaList[i + 1] += 1

for tup in params:
    minNum, maxNum = tup
    result = ruisekiwaList[maxNum + 1] - ruisekiwaList[minNum]
    print(result)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

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

Q = I()
l,r = Line(Q)

def is_prime_all(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 is_prime

prime_judge = is_prime_all(10**5)

a = []
for i in range(10**5):
  if i==0 or i==1 or i==2:
    a.append(0)
  else:
    if i%2==0:
      a.append(a[-1])
    else:
      if (prime_judge[i]==True) and (prime_judge[(i+1)//2]==True):
        a.append(a[-1]+1)
      else:
        a.append(a[-1])

for i in range(Q):
  print(a[r[i]]-a[l[i]-1])

Submission status: Accepted

Solution code:
#前計算
#素数のリスト作成
#必要パラメータ
# ------------------------------------------------------------------
MAX_N = 10 ** 5 + 10 #最低限必要な数 = 10 ** 5 + 1(今回の問題の場合)
# ------------------------------------------------------------------
def primes(n):
    import math
    count_lst = [0] * (n + 1)
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 1):
        if not is_prime[i]: #自分自身が素数出ない時
            count_lst[i] = count_lst[i - 1]
            continue
        #素数のとき
        if i != 2 and is_prime[(i + 1)//2]: #2017数である時
            count_lst[i] = count_lst[i - 1] + 1
        else: #2017数でない時
            count_lst[i] = count_lst[i - 1]
        #ある素数の倍数をすべて素数ではないとする
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    #これ以降は、新しい素数は出てこない
    for i in range(int(math.sqrt(n)) + 1, n + 1):
        if is_prime[i] and is_prime[(i + 1)//2]: #条件を満たす時
            count_lst[i] = count_lst[i - 1] + 1
        else:
            count_lst[i] = count_lst[i - 1]

    return count_lst
    # return [i for i in range(n + 1) if is_prime[i]]

count_lst = primes(MAX_N)
# print (count_lst[:20])
#答える部分
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print (count_lst[r] - count_lst[l - 1]) #累積和の全体 - 累積和の不要部分

Submission status: Accepted

Solution code:
Q = int(input())
LR = [list(map(int,input().split())) for _ in [0]*Q]

N = max(r for l,r in LR)

p = []
for i in range(3,N+1,2):
    for j in p:
        if i%j==0: break
        if j*j>i:
            p.append(i)
            break
    else:
        p.append(i)
p.append(2)
p = set(p)

c = [0]*(N+1)
for i in p:
    if (i+1)//2 in p:c[i] = 1

class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

Sc = cumulative_sum(c)

for l,r in LR:
    print(Sc.get(l,r+1))

Submission status: Accepted

Solution code:
import numpy as np

q = int(input())

# 高速素数判定
is_prime = np.ones(100001, dtype=int)
is_prime[0]=0
is_prime[1]=0

for i in range(2,100001):
    if is_prime[i]==1:
        j=i+i
        while j <= 100000:
            is_prime[j] = 0
            j += i

like2017 = [1 if is_prime[i] and is_prime[(i+1)//2] else 0 for i in range(0,100001) ]

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

Submission status: Accepted

Solution code:
import numpy as np

q = int(input())

# 高速素数判定
is_prime = np.ones(100001, dtype=int)
is_prime[0]=0
is_prime[1]=0

for i in range(2,100001):
    if is_prime[i]==1:
        j=i+i
        while j <= 100000:
            is_prime[j] = 0
            j += i

like2017 = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,100001)]

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

Submission status: Accepted

Solution code:
import numpy as np
n=123456
q = int(input())
 
is_prime = np.ones(n+1,dtype=int)
is_prime[0]=0
is_prime[1]=0
 
for i in range(2,n+1):
    if(is_prime[i]==1):
        j=i+i
        while j <= n:
            is_prime[j] = 0
            j += i
 
cnt = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,n+1)]
 
for i in range(1,n+1):
    cnt[i]+=cnt[i-1]
 
for i in range(q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC84 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

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

ansprime = [float('inf')]*(10**5)
for i in range(1,10**5+1,2):
    if is_prime[i] and is_prime[(i+1)//2]:
        ansprime[i] = i
ansprime.sort()
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    li = bisect.bisect_left(ansprime,l)
    ri = bisect.bisect_right(ansprime,r)
    print(ri-li)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def main():
    Q = int(input())
    lr = []
    for i in range(Q):
        l, r = map(int,input().split())
        lr.append((l,r))
        
    mapd = []
    for i in range(0, 100001):
        if i == 0:
            mapd.append(0)
            continue
        if i == 1:
            mapd.append(0)
            continue
        if i % 2 == 0:
            mapd.append(mapd[i-1])
            continue
        if is_prime(i) and is_prime((i+1)/2):
            mapd.append(mapd[i-1] + 1)
        else:
            mapd.append(mapd[i-1])
            
        
    for i in lr:
        l, r = i
        print(mapd[r] - mapd[l-1])
    
def is_prime(n): 
    i = 2
    while i * i <=n:
        if n % i == 0:
            return False
        i += 1
    return True
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
q = int(input())
fact = [1]*(10**5+7)
fa_sum = [0]*(10**5+7)
fact[0] = 0
fact[1] = 0

for i in range(2,10**5+7):
  if fact[i]:
    for j in range(i*2,10**5+7,i):
      fact[j] = 0
  if fact[i] and fact[(i+1)//2]:
    fa_sum[i] = fa_sum[i-1] + 1
  else:
    fa_sum[i] = fa_sum[i-1]

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

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
q = int(stdin.readline().rstrip())
l_r = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
max_n = 0
for s in l_r:
    max_n = max(s[1], max_n)
# print(max_n)
# print(l_r)
# b : isPrime
b = [1] * (max_n+1)
b[0] = 0
b[1] = 0
# エラトステネスのふるい
for i in range(2,max_n+1):
    if b[i]:
        j = i*2
        while j <= max_n:
            b[j] = 0
            j += i
# print(b)
c = [1 if x == 1 and b[int((i+1)/2)] == 1 else 0 for i,x in enumerate(b)] 
# print(c)
s = list(accumulate(c))
# print(len(s))

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

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
q = int(stdin.readline().rstrip())
l_r = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
max_n = 0
for s in l_r:
    max_n = max(s[1], max_n)
# print(max_n)
# print(l_r)

a = [i for i in range(max_n+1)]

def isPrime(num):
    if num == 0 or num == 1:
        return False
    ans = True
    for i in range(2,int(num/2)+1):
        if num % i == 0:
            ans = False
            break
    return ans
b = [1] * (max_n+1)
b[0] = 0
b[1] = 0
for i in range(2,max_n+1):
    if b[i]:
        j = i*2
        while j <= max_n:
            b[j] = 0
            j += i
# print(b)
c = [1 if x == 1 and b[int((i+1)/2)] == 1 else 0 for i,x in enumerate(b)] 
# print(c)
s = list(accumulate(c))
# print(len(s))

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

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10**7)


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h(typ) if m > 1 else typ(input()) for _ in range(n)]


def main():
    q, = read_h()
    rng = read_v(q, m=2)

    MAX = 100000

    # Sieve of Eratosthenes
    is_prime = [True] * MAX
    is_prime[0], is_prime[1] = False, False
    for i in range(MAX):
        if not is_prime[i]:
            continue
        for j in range(i * 2, MAX, i):
            is_prime[j] = False

    # Find 2017-like numbers
    a = [0] * (MAX + 1)
    for i in range(MAX + 1):
        if i % 2 == 0:
            continue
        if is_prime[i] and is_prime[(i + 1) // 2]:
            a[i] = 1

    # Calc cumulative sum
    s = [0] * (MAX + 1)
    for i in range(MAX):
        s[i + 1] = s[i] + a[i]

    # Print answers
    for l, r in rng:
        print(s[r + 1] - s[l])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
q = int(input())
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

r_max = max(r) + 10
is_prime = [True] * (r_max+1)
is_prime[0] = is_prime[1] = False
for i in range(2, r_max):
    if is_prime[i]:
        for j in range(2, r_max // i + 1):
            is_prime[i*j] = False

# print(is_prime)
a = [0] * r_max
for i in range(3, r_max):
    a[i] = a[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] += 1
# print(a)

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

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import sqrt
from sys import stdin
MIN, MAX = 10**5+1, 0

def is_prime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False

    i = 3
    while i <= sqrt(x):
        if x % i == 0:
            return False
        i = i + 2
    
    return True

Q = int(stdin.readline().rstrip())

LR = []
for i in range(Q):
    l, r = [int(_) for _ in stdin.readline().rstrip().split()]
    if l < MIN:
        MIN = l
    if r > MAX:
        MAX = r
    LR.append((l, r))

primes = [is_prime(i) and is_prime((i+1)//2) for i in range(MIN, MAX+1)]
primes = [0]+primes
primes = list(accumulate(primes))

for i in range(Q):
    print(primes[LR[i][1] - MIN+1] - primes[LR[i][0] - MIN])

Submission status: Accepted

Solution code:
def is_prime(n):
    if n < 2:
        return 0

    if n == 2:
        return 1

    if n % 2 == 0:
        return 0

    i = 3
    while i * i <= n:
        if n % i == 0:
            return 0
        i += 2

    return 1


A = [is_prime(i) for i in range(1 + 10 ** 5)]
S = [A[i] & A[(i + 1) // 2] for i in range(1 + 10 ** 5)]
T = [0] * (1 + 10 ** 5)
T[0] = S[0]
for i in range(1, 1 + 10 ** 5):
    T[i] = T[i - 1] + S[i]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(T[r] - T[l - 1])

Submission status: Accepted

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

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

Ans = [0]*(10**5 + 10)

for a in range(2,10**5 + 9):
    if prime[a] and prime[int((a+1)/2)]:
        Ans[a] = 1
    Ans[a] += Ans[a-1]

for l,r in LR:
    print(Ans[r]-Ans[l-1])

Submission status: Accepted

Solution code:
def shave(n):
    n_root = int(n**0.5)
    candidate = [i for i in range(3,n+1,2)]
    for i in range(3,n_root+2,2):
        candidate = [ j for j in candidate if j == i or j % i != 0]   
    candidate = [2] + candidate
    return candidate


def cumsum(inlist):
    s = 0
    outlist = []
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist

prime_list = shave(100000)

prime_or_not_prime_list = [ 0 for i in range(10**5+1) ]
like_2017_list = [ 0 for i in range(10**5+1) ]
for i in prime_list:
    prime_or_not_prime_list[i] = 1
    j = (i + 1) // 2
    if prime_or_not_prime_list[j] == 1:
        like_2017_list[i] = 1
like_2017_list_sum = cumsum(like_2017_list)


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

Submission status: Accepted

Solution code:
def sieve(N):
    global table,prime
    table = [True]*(N+1)
    table[0] = False
    table[1] = False
    prime = []
    for i in range(2,N+1):
        if table[i]:
            prime.append(i)
            for j in range(2*i,N+1,i):
                table[j] = False

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r+1] - cs[l]

Q = int(input())

sieve(10**5)

def judge(x):
    return x % 2 and table[x] and table[(x+1)//2]

flag = [judge(x) for x in range(0,10**5+1)]

accmulate(flag)

ans_list = []

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

print(*ans_list, sep="\n")

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 is_prime

def main():
    q=int(input())
    is_prime = primes(10**5+1)
    a = [0 for i in range(10**5+1)]
    for i in range(3,10**5+1):
        if is_prime[i] and is_prime[(i+1)//2]:a[i]+=1
    for i in range(3,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:
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 is_prime

def main():
    q=int(input())
    is_prime = primes(10**5+1)
    a = [0 for i in range(10**5+1)]
    for i in range(3,10**5+1):
        if is_prime[i] and is_prime[(i+1)//2]:
            a[i]+=1

    for i in range(3,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:
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 is_prime

def main():
    q=int(input())
    is_prime = primes(10**5+1)
    a = [0 for i in range(10**5+1)]
    for i in range(3,10**5+1):
        if is_prime[i] and is_prime[(i+1)//2]:
            a[i]=a[i-1]+1
        else:
            a[i]=a[i-1]

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

main()

Submission status: Accepted

Solution code:
from itertools import accumulate
Q = int(input())

def sieve(n):
    if n == 0:
        return [False]

    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    
    for i in range(2, n + 1):
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
                
    return is_prime

MAX = 10 ** 5
is_prime = sieve(MAX)
cnt = [0] * (MAX + 1)
for i in range(MAX + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        cnt[i] = 1
cnt = list(accumulate(cnt))

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

Submission status: Accepted

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

sosuu=[2]
s=sosuu.append
for i in range(1,50001):
	k=2*i+1
	for j in sosuu:
		if k%j==0:
			break
		elif j>320:
			s(k)
			break
	else:
		s(k)

sosuu2=set(sosuu)
num=[]
n=num.append
for i in sosuu:
	k=(i+1)//2
	if k in sosuu2:
		n(i)

lis=[0]*100000

for i in num:
	lis[i-1]=1
	
from itertools import accumulate
lis=[0]+list(accumulate(lis))

for i in range(q):
	l,r=lr[i]
	print(lis[r]-lis[l-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
Q = int(input())

def prime(n):
    # 素数列挙
    # nまでの素数をリストで返す(nを含む)
    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)
    return primes

prime_set = set(prime(10**5))
ans = []

for i in range(10**5+1):
    if i%2 == 0:
        ans.append(0)
    else:
        if i in prime_set and (i+1)//2 in prime_set:
            ans.append(1)
        else:
            ans.append(0)
ans = list(accumulate(ans))

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

Submission status: Accepted

Solution code:
q=int(input())
LR=[[int(i) for i in input().split()] for _ in range(q)]
sosu=[False]*(10**5+1)
question=[0]*(10**5+1)
for i in range(2,10**5+1):
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            break
    else:
        sosu[i]=True
for i in range(3,10**5+1):
    if sosu[i] and sosu[(i+1)//2]:
        question[i]=1
for i in range(1,10**5+1):
    question[i]+=question[i-1]
for l,r in LR:
    print(question[r]-question[l-1])

Submission status: Accepted

Solution code:
max_num = 10**5+5
eratos_thenes_sieve = [0,0] + [1]*max_num
n = 2 #素数
while n*n <= max_num:
  if eratos_thenes_sieve[n]:#
    for i in range(2*n, max_num, n):
      eratos_thenes_sieve[i] = 0
  n += 1
  
isLike2017 = [0] * max_num
cumulativeSums = [0]
for i in range(max_num):
  if eratos_thenes_sieve[i] and eratos_thenes_sieve[(i+1)//2]:
    isLike2017[i] = 1
  cumulativeSums.append(cumulativeSums[-1] + isLike2017[i])
  
  
q = int(input())

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

Submission status: Accepted

Solution code:
def sieve(n):
    prime=[]
    is_prime=[True]*(n+1)
    is_prime[0]=False
    is_prime[1]=False
    for i in range(2,n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(2*i,n+1,i):
                is_prime[j]=False
    return is_prime
prime=sieve(10**5)
prime1=[False]*(10**5+1)
for i in range(10**5+1):
    if prime[i]:
        if 1<=i*2-1<=10**5:
            prime1[i*2-1]=True
prime2=[0]*(10**5+1)
for i in range(10**5+1):
    if prime[i] and prime1[i]:
        prime2[i]=1
Sum=[0]*(10**5+1)
for i in range(1,10**5+1):
    Sum[i]=Sum[i-1]+prime2[i]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(Sum[r]-Sum[l-1])

Submission status: Accepted

Solution code:
# 毎回やってもたかがしれてそう -> 間に合いませんでした
# 素直に累積和+包除原理を使う

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


def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True


for i in range(3, 10**5+1):
    if isPrime(i) and isPrime(int((i + 1) / 2)):
        arr[i] = 1
    arr[i] += arr[i-1]

q = int(input())


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

Submission status: Accepted

Solution code:
import itertools
import math
from collections import defaultdict



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

N = int(input())
ps = primes(10**5)

sim2017 = [0] * (10**5 + 1)
di =defaultdict(lambda :False)
for p in ps:
    di[p] = True
for p in ps:
    if di[(p+1)/2]:
        sim2017[p] +=1
l = len(sim2017)
for i in range(1,l):
    sim2017[i] = sim2017[i-1] + sim2017[i]
ins = []
for i in range(N):
    a,b = list(map(int,input().split(" ")))
    ins.append((a,b))
for a,b in ins:
    print(sim2017[b] - sim2017[a-1])