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:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    Q = Scanner.int()
    L = [0] * Q
    R = [0] * Q
    for i in range(Q):
        L[i], R[i] = Scanner.map_int()
    MAX = int(1e05) + 10
    sums = [0] * MAX
    for n in range(MAX - 1):
        sums[n+1] = sums[n]
        if n % 2 == 1 and Math.isPrime(n) and Math.isPrime((n + 1) // 2):
            sums[n+1] += 1
    for i in range(Q):
        print(sums[R[i] + 1] - sums[L[i]])
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

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

sosu_list = primes(10**5+7)

like2017 = [0] * (10**5+7)
for i in range(len(sosu_list)-1):
    if i % 2 == 1 and sosu_list[i]:
        if sosu_list[(i+1)//2]:
            like2017[i] = like2017[i-1] + 1
            continue
    like2017[i] = like2017[i-1]

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

Submission status: Accepted

Solution code:
MAX= 101010
is_prime = [ 1 ] * MAX
is_prime[0] = is_prime[1] = 0
for i in range( MAX ):
    if is_prime[ i ] == 0:
        continue
    for j in range( 2 * i, MAX, i ):
        is_prime[ j ] = 0

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

s = [ 0 ] * MAX
for i in range( 1, MAX ):
  s[ i ] = s[ i - 1 ] + a[ i ]

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

Submission status: Accepted

Solution code:
import math
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
n= 10**5
#エラストテネスのふるい
is_prime=[True]*(n+1)
is_prime[0]=is_prime[1]=False
for i in range(2,int(math.sqrt(n))+1):
	if is_prime[i]:
		for j in range(2*i,n+1,i):
			is_prime[j]=False
L=[0,0]
c=0
for i in range(2,n+1):
	if is_prime[i] and is_prime[(i+1)//2]:
		c += 1
	L.append(c)
for l,r in lr:
	print(L[r]-L[l-1])

Submission status: Accepted

Solution code:
Q=int(input())

n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

from bisect import bisect_left,bisect_right
import numpy as np

ls=[]
rs=[]
for i in range(Q):
    l,r=map(int, input().split())
    ls.append(l)
    rs.append(r)
lmin=min(ls)
rmax=max(rs)
bool_prime=np.zeros(rmax+1,dtype=np.int64)
bool_2007=np.zeros(rmax+1,dtype=np.int64)

for p in primes:
    if p>rmax:
        break
    bool_prime[p]=1
    if p!=2 and bool_prime[(p+1)//2]==1:
        bool_2007[p]=1

cum2007=np.cumsum(bool_2007)
for i in range(Q):
    print(cum2007[rs[i]]-cum2007[ls[i]-1])

Submission status: Accepted

Solution code:
import numpy as np
U = 10**5+10
T = np.zeros(U, np.bool)
T[1] = 1
T[2] = 1
T[3::2] = 1
for i in range(3,U,2):
  if i*i>U:
    break
  if T[i]:
    T[i*i::i+i] = 0
A = np.zeros(U, np.bool)
for i in range(3,U,2):
  if T[i]==1 and T[(i+1)//2]==1:
     A[i] = 1
A[1] = 0
A[2] = 0
A = A.cumsum()
    
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  print(A[r]-A[l-1])

Submission status: Accepted

Solution code:
import sys
import bisect

input = sys.stdin.readline


def get_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 = int(input())
    lr = [[int(x) for x in input().split()] for _ in range(Q)]

    P = get_primes(10 ** 5 + 1)
    setP = set(P)
    like = []
    for p in P:
        if (p + 1) // 2 in setP:
            like.append(p)


    for l, r in lr:
        li = bisect.bisect_left(like, l)
        ri = bisect.bisect_right(like, r)
        print(ri - li)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
from functools import lru_cache

input = sys.stdin.readline


@lru_cache(maxsize=None)
def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


def main():
    Q = int(input())
    lr = [[int(x) for x in input().split()] for _ in range(Q)]

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

    for l, r in lr:
        li = bisect.bisect_left(sosu, l)
        ri = bisect.bisect_right(sosu, r)
        print(ri - li)









if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
Q=int(input())

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

for i in range(2,int(int(10**5)**0.5+1)):
    if PN[i]==1:
        cnt=2
        while i*cnt<10**5+1:
            PN[i*cnt]=0
            cnt+=1

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

for i in range(1,100001,2):
    if PN[i]==1 and PN[(i+1)//2]==1:
        chk[i]=1

S=[0]*(10**5+2)
for i in range(1,10**5+2):
    S[i]=S[i-1]+chk[i-1]

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=100000
primes = set(range(3, N+1, 2))
for i in range(3, int(N**0.5+1)):
  primes.difference_update(range(i*3, N+1, i*2))
primes=set(primes)
primes.add(2)
FG=[0]*(N+1)
for i in range(1,N+1,2):
  FG[i-1]=FG[i-2]
  if i in primes and (i+1)//2 in primes:
    FG[i]=FG[i-1]+1
  else:
    FG[i]=FG[i-1]
for q in range(int(input())):
  l,r=map(int,input().split())
  print(FG[r]-FG[l-1])

Submission status: Accepted

Solution code:
import bisect
prime_check=[True for i in range(100000)]
prime_check[0]=False
prime_check[1]=False

prime_num=[]

for i in range(2,100000):
    if(prime_check[i]):
        prime_num.append(i)
        for j in range(2*i,100000,i):
            prime_check[j]=False

like_num=[]
for pi in prime_num:
    if(prime_check[(pi+1)//2]):
        like_num.append(pi)

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    l_ind=bisect.bisect_left(like_num, l)
    r_ind=bisect.bisect_right(like_num, r)
    print(r_ind - l_ind)

Submission status: Accepted

Solution code:
n = 100000
plist = range(2,n+1)
for i in range(n):
    if plist[i]**2>n:
        break
    plist = [num for num in plist if num % plist[i] != 0 or num == plist[i]]
ok = [0]*n
for p in plist:
    ok[p] += 1
    if p*2-1 < n:
        ok[p*2-1] += 1
li = []
cnt = 0
for i in range(n):
    if ok[i] == 2:
        cnt += 1
    li.append(cnt)
Q = int(input())
qlist = []
for i in range(Q):
    l, r = map(int, input().split())
    qlist.append((l,r))
for x in qlist:
    (l, r) = x
    print(li[r]-li[l-1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

Q = INT()
L = [LIST() for _ in range(Q)]

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

prime = prime_for(10**5)

acc = [0]*10**5
for i in range(1, 10**5):
	if i%2 == 0:
		acc[i] = acc[i-1]
	if prime[i] and prime[int((i+1)/2)]:
		acc[i] = acc[i-1]+1
	else:
		acc[i] = acc[i-1]

for i in range(len(L)):
	print(acc[L[i][1]] - acc[L[i][0]-1])

Submission status: Accepted

Solution code:
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
n = 10 ** 5

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

L = [0, 0]
c = 0
for i in range(2, n + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        c += 1
    L.append(c)

ans = 0

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

Submission status: Accepted

Solution code:
import sys

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')


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

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

    return True


def main():
    Q = INT()
    LR = []

    lmin = INF
    rmax = 0
    for i in range(Q):
        l, r = MAP()
        lmin = l if l < lmin else lmin
        rmax = r if r > rmax else rmax
        LR.append([l, r])

    L = [0] * ((rmax - lmin)//2 + 2)
    for i, n in enumerate(range(lmin, rmax+2, 2)):
        L[i+1] = L[i] + (is_prime(n) and is_prime((n+1)//2))

    for q in range(Q):
        print(L[(LR[q][1] - lmin)//2+1] - L[(LR[q][0] - lmin)//2])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
check = [2]
ans = [0,0]
count = 0
for i in range(3,10**5+1):
    if i % 2 == 0:
        ans.append(count)
    else:
        a = True
        for j in check:
            if j > i**0.5+1:
                break
            if i % j == 0:
                a = False
                break
        if a:
            check.append(i)
            
            if (i+1)//2 in check:  
                count += 1
        ans.append(count)

for i,j in l:
    print(ans[j-1]-ans[max(0,i-2)])

Submission status: Accepted

Solution code:
q=int(input())
M=100000

import math
def erato(n):
    prime=[]
    cnt=[0]*n
    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]

prime=erato(M)
cnt=[0]*M
for i in range(len(prime)):
  cnt[prime[i]]+=0.6
  if 2*prime[i]-1<M:
    cnt[2*prime[i]-1]+=0.6
 
for i in range(1,M):
  if cnt[i]>1:
    cnt[i]=cnt[i-1]//1+1
  else:
    cnt[i]=cnt[i-1]//1
    
#print(cnt)
for i in range(q):
  l,r=map(int,input().split())
  print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
import sys
stdin=sys.stdin
nl_i=lambda: list(map(int, stdin.readline().split()))

def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(input())

b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])


for i in range(q):
 l,r=nl_i()
 print(b[r+1]-b[l])

Submission status: Accepted

Solution code:
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(input())

b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])

import sys
stdin=sys.stdin
temp=lambda: list(map(int, stdin.readline().split()))

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

Submission status: Accepted

Solution code:
def eratosthenes(n):
 is_p=[1]*n
# p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
#   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p#, p_list

lim=10**5+1
#is_p, p_list=eratosthenes(lim)
is_p=eratosthenes(lim)

q=int(input())

'''
b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])
'''
a = [0] * (10**5+2)
for i in range(3, 10**5+1, 2):
    if is_p[i] and is_p[(i+1)//2]:
        a[i] = 1
for i in range(1, 10**5+1):
    a[i+1] += a[i]

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

Submission status: Accepted

Solution code:
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(input())

'''
b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])
'''
a = [0] * (10**5+2)
for i in range(3, 10**5+1, 2):
    if is_p[i] and is_p[(i+1)//2]:
        a[i] = 1
for i in range(1, 10**5+1):
    a[i+1] += a[i]

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

Submission status: Accepted

Solution code:
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(input())

b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])

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

Submission status: Accepted

Solution code:
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

# return p_list
 return is_p

q=int(input())

lim=10**5+1
is_p=eratosthenes(lim)

#print(is_p)

b=[0]
for i in range(1,lim+1):
 if is_p[i-1]==1 and is_p[i//2]==1:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])

#print(b)

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

Submission status: Accepted

Solution code:
# D - 2017-like Number
def isPrime(p):
    for i in range(2, int(p**0.5)+1):
        if p % i == 0:
            return False
    return True

q=int(input())
f=[1]*(10**5+1)
f[0],f[1]=0,0

for i in range(2,len(f)):
    if isPrime(i):
        for j in range(i*2,len(f),i):
            f[j]=0

c=[0]*(10**5+1)
for i in range(2,10**5+1):
    if i%2==1:
        if f[i]==1 and f[(i+1)//2]==1:
            c[i]=c[i-1]+1
            continue
        c[i]=c[i-1]
    else:
        c[i]=c[i-1]

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

Submission status: Accepted

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


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

c2017 = [0]
total = 0
for i in range(1, 10**5+1):
    if is_prime(i) and is_prime((i+1)//2):
        total += 1
    c2017.append(total)

for i in range(Q):
    l, r = LR[i]
    ans = (c2017[r] - c2017[l-1])
    print(ans)

Submission status: Accepted

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


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

n2017 = set()
c2017 = [0]
total = 0
for i in range(1, 10**5+1):
    if is_prime(i) and is_prime((i+1)//2):
        total += 1
    c2017.append(total)

for i in range(Q):
    l = L[i]
    r = R[i]
    ans = (c2017[r] - c2017[l-1])
    print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
 p=2
 fcr=[]
 while p*p<=n:
  while n%p==0:
   fcr.append(p)
   n//=p
  p+=1
 if n>1:
  fcr.append(n)
 return fcr

q=int(input())

cnt=1
p_list=[1]
q_list=[0]
for i in range(3,10**5+1,2):
 a=factorization(i)
 b=factorization((i+1)//2)

 if len(a)==len(b)==1:
  cnt+=1
  q_list.append(1)
 else:
  q_list.append(0)

 p_list.append(cnt)

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

 c=p_list[r//2]-p_list[l//2]
 if q_list[l//2]==1:
  print(c+1)
 else:
  print(c)

Submission status: Accepted

Solution code:
import numpy as np
limit = 10**5
def Eratosthenes(limit):
	is_prime = np.full(limit+1, True)
	is_prime[:2] = False
	for p in range(2,limit+1):
		if p**2 > limit:
			break
		if is_prime[p]:
			is_prime[p**2::p] = False

	return is_prime

is_prime = Eratosthenes(limit)

fullfill = np.zeros(limit+1,np.int32)

for p in range(limit+1):
	if p*2+1 > limit:
		break
	elif is_prime[p] and is_prime[2*p-1]:
		fullfill[2*p-1] = 1

ans = np.cumsum(fullfill)

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

print(*A)

Submission status: Accepted

Solution code:
import numpy as np
limit = 10**5
def Eratosthenes(limit):
	is_prime = np.full(limit+1, True)
	is_prime[:2] = False
	for p in range(2,limit+1):
		if p**2 > limit:
			break
		if is_prime[p]:
			is_prime[p**2::p] = False

	return is_prime

is_prime = Eratosthenes(limit)

fullfill = np.zeros(limit+1,np.int32)

for p in range(limit+1):
	if p*2+1 > limit:
		break
	elif is_prime[p] and is_prime[2*p-1]:
		fullfill[2*p-1] = 1

ans = np.add.accumulate(fullfill)

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

print(*A)

Submission status: Accepted

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

def main():
    N = int(input())
    M = 100000
    def sieve(n):
        is_prime = [True for _ in range(n+1)]
        is_prime[0] = False

        for i in range(2, n+1):
            if is_prime[i-1]:
                j = 2 * i
                while j <= n:
                    is_prime[j-1] = False
                    j += i
        return is_prime
    prime = sieve(M)
    alike = [0]
    for i in range(1,M+1,2):
        if (prime[i-1] and prime[(i+1)//2-1]):
            alike.append(alike[-1]+1)
        else:
            alike.append(alike[-1])
            
    for i in range(N):
        l,r = map(int,input().split())
        l = (l+1)//2
        r = (r+1)//2
        print(alike[r]-alike[l-1])
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def f(n):
    flag = [True]*(n+1)
    flag[0] = flag[1] = False
    for i in range(2,int(n**0.5)+1):
        if flag[i]:
            x = 2*i
            while x <= n:
                flag[x] = False
                x += i
    return flag

m = max(rr)
j = f(m)
cnt = [0]*(m+1)
for i in range(1,m+1):
    cnt[i] = cnt[i-1]
    if i%2 != 0 and j[i] and j[(i+1)//2]:
        cnt[i] += 1

for i in range(q):
    print(cnt[rr[i]]-cnt[ll[i]-1])

Submission status: Accepted

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

m = min(ll)
M = max(rr)
cnt = [0]*(M+2)

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

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

for i in range(q):
    print(cnt[rr[i]]-cnt[ll[i]-2])

Submission status: Accepted

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def main():
    MAX = 10 ** 5
    Q = int(input())

    ans = np.array([0] * (MAX + 1))
    sum = 0
    prime = set()
    memo = np.array([False] * 2 + [True] * (MAX - 1))
    for i in range(2, MAX + 1):
        if memo[i]:
            prime.add(i)
            for j in range(i * 2, MAX + 1, i):
                memo[j] = False
            if (i + 1) // 2 in prime:
                sum += 1
        ans[i] = sum
    
    for _ in range(Q):
        l, r = map(int, input().split())
        print(ans[r] - ans[l-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    MAX = 10 ** 5
    Q = int(input())

    ans = [0] * (MAX + 1)
    sum = 0
    prime = set()
    memo = [False] * 2 + [True] * (MAX - 1)
    for i in range(2, MAX + 1):
        if memo[i]:
            prime.add(i)
            for j in range(i * 2, MAX + 1, i):
                memo[j] = False
            if (i + 1) // 2 in prime:
                sum += 1
        ans[i] = sum
    
    for _ in range(Q):
        l, r = map(int, input().split())
        print(ans[r] - ans[l-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# エネスとテレスのふるい
MAX = int(10e5)
is_prime = [True] * MAX
is_prime[0], is_prime[1] = False, False
for i in range(2, MAX):
    if not is_prime[i]:
        continue
    for j in range(i * 2, MAX, i):
        is_prime[j] = False

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

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

# クエリ処理
Q = int(input())
for i in range(Q):
    l, r = [int(i) for i in input().split()]
    print(s[r + 1] - s[l])

Submission status: Accepted

Solution code:
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
N = 10**5
c = [0] * (N+1)
tf = [False] * (N+1)

for i in range(2, N+1):
    if not tf[i]:
        for j in range(i*2, N+1, i):
            tf[j] = True
for i in range(3, N, 2):
    if not tf[i] and not tf[(i+1)//2]:
        c[i] += 1

for i in range(3, N, 1):
    c[i] += c[i-1]
for l, r in lr:
    print(c[r] - c[l-1])

Submission status: Accepted

Solution code:
import itertools
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)


# 素数
# Eratosthenesの篩

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

M = 10 ** 5 + 1
is_prime = np.ones(M, np.bool)
is_prime2 = np.ones(M, np.bool)
is_prime[1] = 0

for i in range(2, M):
    if i*i > M:
        break

    if is_prime[i]:
        is_prime[i+i::i] = 0

for i in range(3, M, 2):
    n = (i+1)//2
    is_prime2[i] = is_prime[n]

is_near_2017 = np.ones(M, np.bool)
is_near_2017[2::2] = 0
is_near_2017[1] = 0

for i in range(3, M, 2):
    is_near_2017[i] = is_prime[i] & is_prime2[i]

#cnt = list(itertools.accumulate(is_near_2017))
cnt = np.cumsum(is_near_2017)

ans = []
for l, r in LR:
    a = cnt[r] - cnt[l-1]
    ans.append(str(a))

print("\n".join(ans))

Submission status: Accepted

Solution code:
N = 10**5
prime_list = [True] * (N+1)        # True が素数
count_list = [0] * (N+1)
for i in range(2, N+1, 1):
    if prime_list[i]:
        for j in range(i+i, N+1, i):
            prime_list[j] = False

for i in range(3, N+1, 2):
    if prime_list[i] and prime_list[(i+1)//2]:
        count_list[i] += 1

for i in range(3, N+1, 1):
    count_list[i] += count_list[i-1]

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

Submission status: Accepted

Solution code:
import bisect

def Get_Sieve_of_Eratosthenes(N):
    prime_list = [2]
    limit = int(N ** 0.5)
    numeric_data = [i for i in range(3, N, 2)]
    while True:
        prime = numeric_data[0]
        if prime >= limit:
            return prime_list + numeric_data
        prime_list.append(prime)
        numeric_data = [x for x in numeric_data if x % prime != 0]

def Get_2017_like_number(N, prime_list):
    ans_list = []
    for p in prime_list:
        if (p+1)//2 in prime_list:
            ans_list.append(p)
    return ans_list


def main():
    N = 10 ** 5
    prime_list = Get_Sieve_of_Eratosthenes(N)
    like_number_list = Get_2017_like_number(N, prime_list)

    # 入力
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    
    for q in Query:
        l = q[0]
        r = q[1]
        print(bisect.bisect_right(like_number_list, r) - bisect.bisect_left(like_number_list, l))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

Q = iin()
lr = [iln() for _ in range(Q)]
max_num = 10**5
def sieves_of_e(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

primes = sieves_of_e(max_num)

c = [0 for _ in range(max_num+2)]
for i in range(max_num+1):
    c[i+1] = c[i]
    if i % 2 == 1 and primes[i] and primes[(i+1)//2]: c[i+1] += 1

for i in range(Q):
    left = lr[i][0]
    right = lr[i][1]+1
    print(c[right]-c[left])

Submission status: Accepted

Solution code:
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
max_v = 10**5
def is_prime(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 = is_prime(max_v)
c = [0 for _ in range(max_v+1)]
for i in range(max_v):
    c[i+1] = c[i]
    if i % 2 == 1 and prime[i] and prime[((i+1)//2)]: 
        c[i+1] += 1
for i in range(Q):
    l = lr[i][0]
    r = lr[i][1]
    print(c[r+1] - c[l])