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())
lr=[tuple(map(int,input().split())) for _ in range(q)]

n=10**5
ansl=[]
sieve=[1]*(n+1)
sieve[0],sieve[1]=0,0
for i in range(2,n):
  if sieve[i]:
    sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
ans=[0]*(n+1)
for i in range(3,n):
  if sieve[i]==1 and sieve[(i+1)//2]==1:
    ans[i]=ans[i-1]+1
  else:
    ans[i]=ans[i-1]

for e in lr:
  print(ans[e[1]]-ans[e[0]-1])

Submission status: Accepted

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

n=10**5
ansl=[]
sieve=[1]*(n+1)
sieve[0],sieve[1]=0,0
for i in range(2,n):
  if sieve[i]:
    for j in range(2*i,n+1,i):
      sieve[j]=0
ans=[0]*(n+1)
for i in range(3,n):
  if sieve[i]==1 and sieve[(i+1)//2]==1:
    ans[i]=ans[i-1]+1
  else:
    ans[i]=ans[i-1]

for e in lr:
  print(ans[e[1]]-ans[e[0]-1])

Submission status: Accepted

Solution code:
from math import gcd
from collections import deque
from bisect import bisect_left,bisect_right

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

rmax=max(e[1] for e in lr)
anslst=[]
candlst=deque([2])
pprod=2
for i in range(3,rmax+1,2):
  tmp=2*candlst[0]-1
  if gcd(pprod,i)==1: 
    candlst.append(i)
    pprod*=i
    if tmp==i:
      anslst.append(tmp)
  if tmp==i:
    candlst.popleft()

for e in lr:
  print(bisect_right(anslst,e[1])-bisect_left(anslst,e[0]))

Submission status: Accepted

Solution code:
Q = int(input())

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

n_max = 10**5

prime = []
data = [i for i in range(2,n_max+1)]
limit = n_max**(1/2)

while True:
    p = data[0]
    if limit<=p:
        break
    prime.append(p)
    data = [i for i in data if i%p!=0]

prime = prime +data

ans_ls = [0]*(1+n_max)
for i in prime:
    if (i + 1) // 2 in prime:
        ans_ls[i] = 1

ans_cs = [0]*(1+n_max)
for i in range(n_max):
    ans_cs[i+1] = ans_cs[i]+ans_ls[i+1]
    
for l,r in ls:
    print(ans_cs[r]-ans_cs[l-1])

Submission status: Accepted

Solution code:
q=int(input())

import math
import numpy as np
def primes(x):
    if x < 2: return []

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

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

    return [prime for prime in primes if prime != 0]



numbers=[0]*100000
prime=primes(100_000)

for j in prime:
    numbers[j-1]=1

deci=numbers.copy()

for p in prime:
    n_2 = (p+1)//2

    if deci[n_2-1]==1:
        continue
    else:
        numbers[p-1]=0

cum=np.cumsum(numbers)

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

    if l==1:
        ans=cum[r-1]
    else:
        ans=cum[r-1] - cum[l-2]

    print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy

def sosu(n):
    so = [1 for i in range(n+1)]
    so[0], so[1] = 0, 0
    for i in range(2, n+1):
        if so[i]:
            for j in range(2, n//i):
                so[i * j] = 0

    return so

def solve():
    # n, k = getList()
    # nums = getList()
    so = sosu(200000)
    ok = [0 for i in range(200000)]

    for i in range(1, 200000):
        if i % 2:
            if so[i] and so[int((i+1) // 2)]:
                ok[i] = 1

    for i in range(1, 200000):
        ok[i] += ok[i-1]
    # print(so)
    # print(ok)
    q = getN()
    for i in range(q):
        l, r = getList()
        print(ok[r] - ok[l-1])




def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
# 69

import itertools
import bisect

q = int(input())
lr_l = [[int(x) for x in input().split()] for y in range(q)]

n_max = max(itertools.chain.from_iterable(lr_l))

isp_l = [True] * (n_max+1)
isp_l[0] = False
isp_l[1] = False

for i in range(2, int(n_max ** 0.5 + 2)):
    if not isp_l[i]:
        continue
    for j in range(i * 2, n_max + 1, i):
        isp_l[j] = False

p_l = [int(x) for x in range(n_max+1) if isp_l[x]]

l_l = []
for i in range(len(p_l)):
    if (p_l[i]+1)//2 in p_l:
        l_l.append(p_l[i])

for i in range(q):
    _l,_r = lr_l[i]
    _s = bisect.bisect_left(l_l, _l)
    _e = bisect.bisect_right(l_l, _r)
    print(_e-_s)

Submission status: Accepted

Solution code:
Q=int(input())

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

nmax = 10**5+1
like = [False]*nmax
for n in range(1,nmax,2):
    if isprime(n) and isprime((n+1)//2):
        like[n]=True

rui = [0]*nmax
rui[0]=int(like[0])
for i in range(1,nmax):
    rui[i] = rui[i-1]+like[i]

for i in range(Q):
    l,r = map(int,input().split())
    print(rui[r]-rui[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

n=10**5
a=seachPrimeNum(n)
b=[]
y=0
x=0
while x<=100000:
  t=a[y]
  x=t*2-1
  b.append(x)
  y+=1
  
c=set(a)&set(b)

q=int(input())
r=[0 for _ in range(100000)]
for f in c:
  r[f]=1
for g in range(len(r)-1):
  r[g+1]=r[g]+r[g+1]

for p in range(q):
  w,z=map(int,input().split())
  print(r[z]-r[w-1])

Submission status: Accepted

Solution code:
def is_prime(n):
    max_factor = int(n**.5)
    for i in range(2, max_factor+1):
        if n % i == 0:
            return False
    return True
  
def is_2017like(n):
    if n % 2 == 0: return False
    return is_prime(n) and is_prime((n+1)//2)
  
cum = [0,0]
for i in range(2,10**5+2):
    if is_2017like(i):cum.append(cum[-1]+1)
    else:cum.append(cum[-1])

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

Submission status: Accepted

Solution code:
def prime(n):
    p = []
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                flag[num] = False
                num += i + 2
    return set(p)

p1 = prime(10 ** 5)
p2 = [0]
for i in range(10 ** 5):
    if i % 2 == 1:
        p2.append(p2[-1])
        continue
    else:
        if i + 1 in p1 and (i + 2) // 2 in p1:
            p2.append(p2[-1] + 1)
        else:
            p2.append(p2[-1])
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(p2[r] - p2[l -1])

Submission status: Accepted

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    def primes(n):
        is_prime = [True] * (n + 1)
        is_prime[0], is_prime[1] = False, False
        for i in range(2, int(n**0.5) + 1):
            if not is_prime[i]:
                continue
            for j in range(i * 2, n + 1, i):
                is_prime[j] = False
        return [i for i in range(n + 1) if is_prime[i]], is_prime

    q = int(input())
    primes_num, is_primes = primes(10**5+5)
    sums = []
    cnt = 0

    for i in range(0, 10**5+4):
        if i%2!=0:
            a = (i+1)//2
            if is_primes[i] and is_primes[a]:
                cnt += 1
        sums.append(cnt)

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

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
import math
m = 10**5

L = [x for x in range(2,m+1)]

#エラトステネスのふるいで素数を抽出
for y in range(2, int(math.sqrt(m)+1)):
    L = [z for z in L if(z == y or z % y != 0)]

#N+1/2も素数であるものを抽出
P = []
for w in L:
    if (w+1)/2 in L:
        P.append(w)

#累積和のために作成
G = [0] * (m+1)
for i in P:
    G[i+1] = 1

#累積和
Q = list(accumulate(G))



n = int(input())
for _ in range(n):
    s, t = map(int, input().split())
    print(Q[t+1]-Q[s])




'''
この素数判定は遅い。
上のようにエラトステネスの篩を使う

def isPrime(n):

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

'''

Submission status: Accepted

Solution code:
import itertools


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


def main():
    Q = int(input())
    LR = [list(map(int, input().split())) for _ in range(Q)]
    N = 10 ** 5

    primes = set(get_sieve_of_eratosthenes(N))

    t = [0 for _ in range(N + 1)]
    for p in primes:
        a, b = divmod(p + 1, 2)
        if b == 0 and a in primes:
            t[p] += 1

    t = list(itertools.accumulate(t))

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


main()

Submission status: Accepted

Solution code:
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int type.")
    if n < 2:
        raise ValueError("n is more than 2")
    prime = [2]
    limit = int(n ** 0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def main():
    Q = int(input())
    LR = [list(map(int, input().split())) for _ in range(Q)]
    N = 10 ** 5

    primes = get_sieve_of_eratosthenes(N)

    t = [0 for _ in range(N + 1)]
    for p in primes:
        a, b = divmod(p + 1, 2)
        if b == 0 and a in primes:
            for i in range(p, N + 1):
                t[i] += 1

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


main()

Submission status: Accepted

Solution code:
def sieve(n):
    is_prime =[True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i+i,n,i):
                is_prime[j] = False
    c = [0 for i in range(n+1)]
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[(i+1)//2]:
            c[i] = 1
    for i in range(n):
        c[i+1] += c[i]
    return c

def solve(l,r,c):
    return c[r]-c[l-1]



if __name__ == '__main__':
    q = int(input())
    c = sieve(100000)
    for i in range(q):
        l,r = map(int,input().split())
        print(solve(l,r,c))

Submission status: Accepted

Solution code:
l=[0]*(10**5)
for i in range(1,10**5+1):
  for j in range(2,int(i**0.5)+1):
    if i%j==0:
      break
  else:
    l[i-1]=1
  
d=[0]*(10**5)
t=3
while t<=10**5:
  if l[t-1]==1 and l[(t-1)//2]==1:
    d[t-1]=1
  t+=2

r=[0]*(10**5+1)
for i in range(10**5):
  r[i+1]=r[i]+d[i]
  

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

Submission status: Accepted

Solution code:
n = int(raw_input())
primes = [True] * ((10 ** 5) + 1)
for t in range(2,len(primes)):
	if primes[t]:
		k = 2
		while(k*t < len(primes)):
			primes[k*t] = False
			k +=1
dp = [0] * ((10 ** 5) + 1)
count = 0

for i in range(2,len(primes)):
	if primes[i] and primes[(i+1)/2] and i % 2:
		count +=1
	dp[i] = count
for _ in range(n):
	u,v = map(int, raw_input().split())
	print dp[v] - dp[u-1]

Submission status: Accepted

Solution code:

def primes(n):
    candidate = list(range(2, n+1))
    prime = []
    limit = n**0.5 + 1
    while True:
        p = candidate[0] 
        if limit <= p:
            prime.extend(candidate)
            break
        prime.append(p)

        candidate = [i for i in candidate if i % p != 0]
    return prime
L=primes(100000)
R=set([i for i in L if (i+1)//2 in L])
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  print(len([i for i in R if i>=a and i<=b]))

Submission status: Accepted

Solution code:
Q = int(input())
Pr = [0]*(10**5+1)
Ta = [0]*(10**5+1)
Tb = [0]*(10**5+1)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

for k in range(10**5+1):
    s = 10**5-k
    if s%2==1:
        if Pr[s]==1:
            continue
        div = make_divisors(s)
        if len(div)==2:
            Pr[s]=1
        div = make_divisors((s+1)//2)
        if len(div)==2:
            Pr[(s+1)//2]=1

for k in range(10**5+1):
    if Pr[k]==1 and Pr[(k+1)//2]==1:
        Ta[k]=1

Tb[1]=0
for k in range(3,10**5+1):
    Tb[k]=Ta[k]+Tb[k-2]

for i in range(Q):
    L,R = list(map(int,input().split()))
    if L==1:
        X = 0
    else:
        X = Tb[L-2]
    Y = Tb[R]
    print(Y-X)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	pp = [1]*(10**5 + 1)
	pp[0]=0
	pp[1]=0
	for i, _ in enumerate(pp):
		if pp[i]==0:
			continue
		st = i
		while st * i < len(pp):
			pp[st*i]=0
			st+=1
	like = pp[:]
	like[2]=0
	for i, v in enumerate(pp):
		
		if v == 1 and i != 2 and pp[(i+1)//2 ] == 0:
			like[i] = 0
	ss = [0] * len(pp)
	for i, v in enumerate(ss[:-1]):
		ss[i+1] = like[i+1]+ss[i]
	#pa(like[:10])
	q = int(input())
	#b , c = tin()
	#s = input()
	for _ in range(q):
		l, r = tin()
		print(ss[r] - ss[l-1])
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# エラトステネスの篩, 累積和
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

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

Q = int(input())
result = []
for _ in range(Q):
    l, r = map(int, input().split())
    result.append(cs[r] - cs[l - 1])
print(*result, sep='\n')

Submission status: Accepted

Solution code:
q = int(input())

L = [True] * (10**5 + 1)

L[0], L[1] = False, False

for i in range(2, int((10**5) ** 0.5) + 1):
    if not L[i]:
        continue
    j = 2
    while i * j <= 10**5:
        L[i * j] = False
        j += 1

A = [0] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    if L[i] and L[(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())
    if l == r:
        if L[l] and L[(l+1)//2]:
            print(1)
        else:
            print(0)
    else:
        if L[l] and L[(l+1)//2]:
            print(A[r] - A[l-1])
        else:
            print(A[r] - A[l])

Submission status: Accepted

Solution code:
import math
from itertools import accumulate
q=int(input())
l=[]
r=[]
for i in range(q):
  a,b=list(map(int,input().split()))
  l.append(a)
  r.append(b)
  
def is_prime(n):
  if n==1:
    return False
  elif n==2:
    return True
  else:
    for i in range(2,int(math.sqrt(n)+1)):
      if n%i==0:
        return False
  return True

l_min=min(l)
r_max=max(r)
ruiseki=[]
for i in range(l_min,r_max+1):
  if i%2==1 and is_prime(i) and is_prime((i+1)//2):
    ruiseki.append(1)
  else:
    ruiseki.append(0)
    
ruiseki=[0]+list(accumulate(ruiseki))

for i in range(q):
  print(ruiseki[r[i]-l_min+1]-ruiseki[l[i]-l_min])

Submission status: Accepted

Solution code:
import sys


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

MAX = 0
for i in range(Q):
    l, r = map(int, input().split())
    MAX = max(MAX, l, r)
    pair.append((l, r))

N = 101010
N = 25
N = MAX + 1
is_prime = [1 for i in range(N)]

is_prime[0] = is_prime[1] = 0

# sieve
for i in range(2, N):
    if not is_prime[i]:
        # 0, 1, 4, 6, 9, ...
        continue
    for j in range(i*2, N, i):
        #print(j)
        is_prime[j] = 0
#print('sieve')
#print(is_prime)

# 2017-like
a = [0 for i in range(N)]
for i in range(N):
    if i % 2 == 0:
        continue
    if is_prime[i] and is_prime[(i+1) // 2]:
        a[i] = 1
#print('2017')
#print(a)

# accum
s = [0]
for i, n in enumerate(a):
    s.append(s[i] + n)
s.pop(0)
#print('accum')
#print(s)

# Query
#print(pair)
#print('ANS')
for l, r in pair:
    print(s[r] - s[l-1])

Submission status: Accepted

Solution code:
import math

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

sosuu=[]
for i in range(1,10**5,2):
  if is_prime(i):
    if is_prime((i+1)//2):
      sosuu.append(i)
sosuu1=[0]*(10**5+1)
for i in range(2,10**5):
  sosuu1[i]=sosuu1[i-1]
  if i in sosuu:
    sosuu1[i]+=1
N = int(input())
xy = [map(int, input().split()) for _ in range(N)]
x, y = [list(i) for i in zip(*xy)]
for i in range(N):
  print(sosuu1[y[i]]-sosuu1[x[i]-2])

Submission status: Accepted

Solution code:
kMax = 100000
def calc_primes():
    is_prime = [True] * (kMax+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, kMax+1):
        if not is_prime[i]:
            continue
        for k in range(2*i, kMax+1, i):
            is_prime[k] = False
    ans = []
    for i in range(2, kMax+1):
        if is_prime[i]:
            ans.append(i)
    return ans

a = [0] * (kMax+1)

primes = set(calc_primes())

acc = 0
for i in range(1, kMax+1, 2):
    ii = (i+1)//2
    if i in primes and ii in primes:
        acc += 1
    a[i] = acc

Q = int(input())

for _ in range(Q):
    l, r = map(int, input().split())
    ra = a[r]
    la = a[l-2] if l >= 3 else 0
    print(ra-la)

Submission status: Accepted

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

p=[]
for i in range(2,100001):
  f=1
  for j in p:
    if j>i**0.5:
      break
    if i%j==0:
      f=0
      break
  if f:
    p.append(i)
p.append(10000000000)
s=[0]
j=0
k=0
for i in range(1,100001,2):
  if p[j]<i:
    j+=1
  if p[k]<(i+1)//2:
    k+=1
  if (i==p[j])and((i+1)//2==p[k]):
    s.append(s[-1]+1)
  else:
    s.append(s[-1])
  s.append(s[-1])

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

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():
    prime = primes(10**5)
    like2017 = [False]*(10**5+1)
    for i in range(1,10**5+1,2):
        if prime[i] and prime[(i+1)//2]:
            like2017[i] = True
    like2017 = np.array(like2017).cumsum()

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
memo =[1]*(10**5+1)
memo[0]=0
memo[1]=0
for i in range(2,len(memo)):
    if memo[i]==0:
        continue
    else:
        for j in range(i*2,len(memo),i):
            memo[j]=0
memo_like2017 = [0]*(10**5+1)
for i in range(3,len(memo),2):
    if memo[i]==1 and memo[(i+1)//2] ==1:
        memo_like2017[i]=1
sum_memo=[0]*(10**5+1)
for i in range(1,len(memo)):
    sum_memo[i] = sum_memo[i-1]+memo_like2017[i]

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product
from itertools import combinations

# input = sys.stdin.readline

def get_prime_list(number):
    is_prime = np.ones(number, dtype=bool)
    is_prime[:2] = False
    num_sqrt = np.sqrt(number) + 1
    for i in range(2, int(num_sqrt) + 1):
        if (is_prime[i]):
            is_prime[i*2::i] = False
    prime_list = np.arange(number)[is_prime]
    return prime_list

Q = int(input())
LRn = [list(map(int, input().split())) for _ in range(Q)]
prime_list = get_prime_list(10**5)
prime_cnt = [0 for _ in range(10**5 + 10)]
for i in range(3, 10**5):
    if i in prime_list:
        if ((i+1)/2) in prime_list:
#             print(i)
            prime_cnt[i] = prime_cnt[i-1] + 1
            continue
    prime_cnt[i] = prime_cnt[i-1]
for LR in LRn:
    print(prime_cnt[LR[1]]-prime_cnt[LR[0]-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.buffer.readline


def sieve(n):
    f = []
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    for i in range(n+1):
        if is_prime[i]:
            f.append(i)
    return f


s = sieve(10**5)
s = set(s)
number_2017 = [0]*(10**5+1)

for i in range(1, 10**5+1):
    if i % 2 == 0:
        continue
    if i in s and (i+1)//2 in s:
        number_2017[i] = 1


acc = list(accumulate(number_2017))

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

Submission status: Accepted

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    max_n = 100005
    is_prime = [True]*max_n
    is_prime[0], is_prime[1] = False, False
    i = 2
    while i*i < max_n:
        if is_prime[i]:
            k = 2
            while i*k < max_n:
                is_prime[i*k] = False
                k+= 1
        i+= 1
        
    table = [0]*max_n
    for i in range(3, max_n):
        table[i] = table[i-1]
        if is_prime[i] and is_prime[(i+1)//2]:
            table[i] += 1
    q = int(input())
    for i in range(q):
        l, r = map(int, input().split())
        tmp = table[r]-table[l]
        if is_prime[l] and is_prime[(l+1)//2]:
            tmp += 1
        print(tmp)



            



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
is_Prime = [True] * (10**5 + 1)
is_Prime[0] = False
is_Prime[1] = False
for i in range(2, int((10**5+1)**0.5)+1):
    for j in range(2*i, 10**5+1, i):
        is_Prime[j] = False
P = [i for i in range(10**5+1) if is_Prime[i] and is_Prime[(i+1)//2]]
odd = [0 for i in range(10**5+2)]
odd[0] = 0
for i in range(1, len(odd)):
    odd[i] = odd[i-1]
    if i in P:
        odd[i] += 1
Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    print(odd[r]-odd[l-1])

Submission status: Accepted

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

Q = int(input())
N = 10**5

prime = eratosthenes(N)
prime_num = [0 for i in range(N+1)]
for p in prime:
    prime_num[p] = 1
    
count = 0
ans = [0 for i in range(N+1)]
for i in range(1, N+1, 2):
    if prime_num[i] == 1 and prime_num[(i+1)//2] == 1:
        count += 1
    ans[i] = count
    
for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l-2])

Submission status: Accepted

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


N = 100000+1
data = get_sieve_of_eratosthenes(N)
flag = [0]*(N+1)
for i in range(len(data)):
    flag[data[i]]=1

for i in range(N,2,-1):
    if i//2==0 or flag[i]!=1 or flag[(i+1)//2]!=1:
        flag[i]=0
flag[2]=0
for i in range(1,N+1,1):
    flag[i] = flag[i]+flag[i-1]

Q = int(input())

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

for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
# n以下の非負整数が素数かどうかを示すリストを返す
def primes(n):
    is_prime = [False] * 2 + [True] * (n - 1)
    for i in [2] + list(range(3, int(n ** 0.5) + 1, 2)):
        if not is_prime[i]: continue
        for j in range(2 * i, n + 1 ,i):
            is_prime[j] = False
    return is_prime

N = 10 ** 5
Q = int(input())
is_prime = primes(N)
cum2017 = [0] * (N + 1) # 累積和
for i in range(1, N + 1):
    cum2017[i] = cum2017[i - 1]
    if i % 2 == 1 and is_prime[i] and is_prime[(i + 1) // 2]:
        cum2017[i] += 1

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

Submission status: Accepted

Solution code:
def primes(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

mx = 10**5
ps = primes(mx)

valid = [0]*(mx+1)

for i in range(3,mx,2):
    if i in ps and (i+1)//2 in ps:
        valid[i] = 1

from itertools import accumulate
acc = list(accumulate(valid))

q,*lr = [list(map(int, s.split())) for s in open(0)]

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

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

def is_prime(n):
    if n == 1:
        return 0
    for k in range(2,int(math.sqrt(n))+1):
        if n % k == 0:
            return 0
    return 1
    
Q = int(input())    
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

min_L = min(L)
max_R = max(R)

check = []
for i in range(min_L,max_R+ 1):
    if (i%2 ==1):
        flg = (is_prime(i) and is_prime((i+1)/2))
    else:
        flg = 0
    check.append(flg)
    
#print(check)

check = [0] + check
check = list(accumulate(check))
#print(check)
#print(R,L,min_L)

for i in range(Q):
    print(check[R[i]-min_L+1]-check[L[i]-min_L])

Submission status: Accepted

Solution code:
from itertools import accumulate

# エラトステネスの篩
def prime_eratosthenes(n):
    prime_list = []
    num_set = set()
    for i in range(2, n + 1):
        if i not in num_set:
            prime_list.append(i)
            for j in range(i * i, n + 1, i):
                num_set.add(j)
    return prime_list


l1 = set(prime_eratosthenes(10 ** 5))
l2 = set()
l3 = [0] * 10 ** 5

for i in l1:
    if (i + 1) // 2 in l1:
        l2.add(i)
for i in l2:
    l3[i] = 1

# 累積和
ans = list(accumulate(l3))


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