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 eratos(num):
    isPrime = [True] * (num + 1)
    isPrime[0] = isPrime[1] = False
    for i in range(2, int(math.sqrt(num))):
        for j in range(2 * i, num, i):
            isPrime[j] = False
    return isPrime


def isLike(isPrime):
    n = len(isPrime)
    array = [False] * (n - 1)
    for i in range(n - 1):
        if isPrime[i] and isPrime[(i + 1) // 2]:
            array[i] = True
    return array


def cumSum(array):
    n = len(array)
    cum = [0] * (len(array))
    for i in range(1, n):
        cum[i] = cum[i - 1]
        cum[i] += 1 if array[i] else 0

    return cum


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


Q = int(input())

isPrime = eratos(10 ** 5 + 1)
array = isLike(isPrime)
cum = cumSum(array)

for i in range(Q):
    l, r = map(int, input().split())
    print(solve(l, r, cum))

Submission status: Accepted

Solution code:
import bisect

b_left = bisect.bisect_left
b_right = bisect.bisect_right
n = 10**5

prime_list = []
is_prime = [True for _ in range(n+1)]
is_prime[0] = False
is_prime[1] = False
for i in range(2, n+1):
    f = is_prime[i]
    if f:
        prime_list.append(i)
        j = 2 * i
        while j <= n:
            is_prime[j] = False
            j += i
like_nums = []
for p in prime_list:
    if 2*p-1 >= n:
        break
    if is_prime[2*p-1]:
        like_nums.append(2*p-1)
#print(like_nums)
Q = int(input())
query = [input() for _ in range(Q)]
for line in query:
    l, r = map(int, line.split())
    a = b_left(like_nums, l)
    b = b_right(like_nums, r)
    print(b-a)

Submission status: Accepted

Solution code:
def isPrime(N):
	"""
	O(sqrt(N))
	"""
	if N<=1:
		return False
	for i in range(2, int(N**.5)+1):
		if N%i==0:
			return False
	return True


prime = [False]*(10**5+1)
for i in range(1,10**5+1):
	prime[i] = isPrime(i)

likely =  [False]*(10**5+1)
for i in range(1, 10**5+1):
	if i%2==1 and prime[i] and prime[(i+1)//2]:
		likely[i] = True

for i in range(1,10**5+1):
	likely[i] += likely[i-1]

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

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

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

N = 10**5

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

prime = [1]*N
prime[0] = prime[1] = 0

for i in range(2,N):
    if prime[i]:
        tmp = i*2
        while tmp < N:
            prime[tmp] = 0
            tmp += i

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

for l in L:
    print(r_sum[l[1]]-r_sum[l[0]-1])

Submission status: Accepted

Solution code:
def is_prime(t):
  i=2
  while i**2<=t:
    if t%i==0:
      return 0
    i+=1
  return 1
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
n=10**5
p=[0]*(n+1)
d=set()
for i in range(2,n):
  if is_prime(i):
    d.add(i)
  if i in d and (i+1)//2 in d:
    p[i]=p[i-1]+1
  else:
    p[i]=p[i-1]
for l,r in lr:
  print(p[r]-p[l-1])

Submission status: Accepted

Solution code:
def is_prime(t):
  i=2
  while i**2<=t:
    if t%i==0:
      return 0
    i+=1
  return 1
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
n=10**5
p=[0]*(n+1)
d=set([])
for i in range(2,n):
  if is_prime(i):
    d.add(i)
  if i in d and (i+1)//2 in d:
    p[i]=p[i-1]+1
  else:
    p[i]=p[i-1]
for l,r in lr:
  print(p[r]-p[l-1])

Submission status: Accepted

Solution code:
import bisect
q=int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
P=primes(10**5+3)
p=set(P)
A=[]
for i in range(len(P)):
  if (P[i]+1)//2 in p:
    A.append(P[i])
for i in range(q):
  a,b=map(int,input().split())
  print(bisect.bisect_right(A,b+1,lo=0,hi=len(A))-bisect.bisect_right(A,a-1,lo=0,hi=len(A)))

Submission status: Accepted

Solution code:
def eratosthenes(n):
    prime = [2]
    if n == 2:
        return prime
    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 solve():
    Q = int(input())
    primes = set(eratosthenes(10 ** 5))
    like_2017 = [0] * (10 ** 5 // 2)
    for i in range(3, 10 ** 5, 2):
        if i in primes and (i + 1) // 2 in primes:
            like_2017[i // 2] = like_2017[i // 2 - 1] + 1
        else:
            like_2017[i // 2] = like_2017[i // 2 - 1]
    for _ in range(Q):
        l, r = map(int, input().split())
        ans = like_2017[r // 2] - like_2017[max(0, l // 2 - 1)]
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def eratosthenes(n):
    prime = [2]
    if n == 2:
        return prime
    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 solve():
    Q = int(input())
    primes = set(eratosthenes(10 ** 5))
    like_2017 = [0] * (10 ** 5 // 2)
    for i in range(3, 10 ** 5, 2):
        if i in primes and (i + 1) // 2 in primes:
            like_2017[i // 2] = like_2017[i // 2 - 1] + 1
        else:
            like_2017[i // 2] = like_2017[i // 2 - 1]
    for _ in range(Q):
        l, r = map(int, input().split())
        if l == 1:
            l = 2
        if r == 1:
            r = 2
        ans = like_2017[r // 2] - like_2017[l // 2 - 1]
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np
q = int(input())

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

s = [False] + [is_prime(i) for i in range(1, 10**5 + 1)]
s = [False] + [s[i] and s[(i + 1) // 2] for i in range(1, 10**5 + 1)]
cs = np.cumsum(s)

results = []
for i in range(q):
    l, r = list(map(int, input().split()))
    results.append(str(cs[r] - cs[l - 1]))
print("\n".join(results))

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def judge_prime_num(n):
    if n % 2 == 0:
        return True
    else:
        for num in range(3, int(math.sqrt(n) + 2)):
            if n % num == 0:
                return False
        return True


Q = int(input())
primes = [2]
checker = []
for i in range(3, 10 ** 5 + 1, 2):
    if judge_prime_num(i) is True:
        primes.append(i)
set_primes = set(primes)
for i in primes:
    if (i+1)//2 in set_primes:
        checker.append(i)
for i in range(Q):
    l, r = map(int,input().split())
    print(bisect.bisect_right(checker, r) - bisect.bisect_left(checker, l))

Submission status: Accepted

Solution code:
import math

def makePrimes(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]

m = 10**5
primes = set(makePrimes(m))
cumulative_sum = [0]*(10**5+1)
for N in range(2,10**5+1):
    cumulative_sum[N] = cumulative_sum[N-1]+1 if N in primes and (N+1)//2 in primes else cumulative_sum[N-1]

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

Submission status: Accepted

Solution code:
n=100000
p=[0]*2+[1]*(n-1)
for i in range(2,n+1):
  if p[i]:
    for j in range(i*2,n+1,i):
      p[j]=0
c=[0]*(n+1)
for i in range(2,n+1)[::-1]:
  if p[i]:
    if p[(i+1)//2]:
      c[i]=1
d=[0]*(n+1)
for i in range(1,n+1):
  d[i]=d[i-1]+c[i]

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

Submission status: Accepted

Solution code:
class Sieve:
    """区間[2,n]の値を素因数分解する"""

    def __init__(self, n=1):
        primes = []
        f = [0] * (n + 1)
        f[0] = f[1] = -1
        for i in range(2, n + 1):  # 素数を探す
            if f[i]: continue
            primes.append(i)
            f[i] = i  # 素数には自身を代入
            for j in range(i * i, n + 1, i):  # 合成数に素因数を書き込む
                if not f[j]:
                    f[j] = i  # 最小の素因数を代入
        self.primes = primes
        self.f = f

    # def is_prime(self, x) -> bool:  # 素数判定
    #     return self.f[x] == x
    #
    # def factor_list(self, x) -> list:  # 素因数分解の昇順リスト, [2,2,3,5,...]
    #     res = []
    #     while x != 1:
    #         res.append(self.f[x])
    #         x //= self.f[x]
    #     return res
    #
    # def factor(self, x) -> list:  # 素因数分解の頻度リスト, [[2,x],[3,y],[5,z],...]
    #     fl = self.factor_list(x)
    #     if not fl: return []
    #     res = [[fl[0], 0]]
    #     for p in fl:
    #         if res[-1][0] == p:
    #             res[-1][1] += 1
    #         else:
    #             res.append([p, 1])
    #     return res


def main():
    import sys

    input = sys.stdin.readline

    sieve = Sieve(10 ** 5)
    prime_set = set(sieve.primes)

    acc = [0] * (10 ** 5 + 1)
    cnt = 0
    for x in range(1, 10 ** 5 + 1):
        if (x % 2 == 1) and (x in prime_set) and ((x + 1) // 2 in prime_set):
            cnt += 1
        acc[x] = cnt

    q = int(input())
    for _ in range(q):
        left, right = map(int, input().split())  # [left,right]<=10**5
        res = acc[right] - acc[left - 1]
        print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

Q=I()

#nまでの素数を列挙(n loglogn)
n = 10**5

#is_prime[i]にはi-1が素数か否かを示すboolが入る，[0]に1の素数判定がある．
is_prime = [True]*(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

table = [ i for i in range(1, n+1) if is_prime[i-1]]

L=[]

for p in table:
    p2=(p+1)//2
    if p2 in table:
        L.append(p)
        
S=[0]*(n+1)

for a in L:
    S[a]+=1
    
for i in range(n):
    S[i+1]+=S[i]
    
    
for i in range(Q):
    l,r=MI()
    print(S[r]-S[l-1])

Submission status: Accepted

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

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 _ in range(Q):
    l, r = map(int, input().split())
    print(s[r+1]-s[l])

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

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


Q = iin()
lr = [iln() for _ in range(Q)]

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

is_primes = sieves_of_e(max_num)

for i in range(1, max_num):
    c[i+1] = c[i]
    if is_primes[i] and is_primes[(i+1)//2]: c[i+1] += 1

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

Submission status: Accepted

Solution code:
# エラトステネスの篩
import math
def Eratosthenes(n):
    if n < 2:
        return None
    prime = [2]
    limit = math.ceil(n**0.5)
    data = list(range(3, n+1, 2))
    p = -1
    while p < limit:
        p = data[0]
        prime.append(p)
        data = [d for d in data if d%p != 0]
    return prime + data

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

r_max = max(R)

# r_maxまでの素数を記録する
memo1 = [0]*(r_max+1)
primes = Eratosthenes(r_max)
for p in primes:
    memo1[p] = 1

# r_maxまでの2017に似た数を記録する
memo2 = [0]*(r_max+1)
for p in primes:
    if (p+1)%2 == 0:
        if memo1[(p+1)//2] == 1:
            memo2[p] = 1
            
# 2017に似た数の累積和
import itertools
accum = list(itertools.accumulate(memo2))

# 出力
for i in range(q):
    print(accum[R[i]] - accum[L[i]-1])

Submission status: Accepted

Solution code:
q = int(input())
primes = [True for _ in range(100000)]
c = [0 for _ in range(100000)]

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

#print(primes[:20])

for i in range(3, 100000, 2):
    if primes[i] and primes[(i+1)//2]:
        c[i] += 1

for i in range(3, 100000):
    c[i] += c[i-1]
#print(c[:20])

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

Submission status: Accepted

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

"""素数判定はこっち"""
def factrize(n):
    b = 2
    while b*b <= n:
        if n % b == 0:
            return False
        b = b+1
    return True

f = []

for i in range(3,10**5+2,2):
    if factrize(i):
        if factrize((i+1)//2):
            f.append(i)
q = int(readline())
for _ in range(q):
    l,r = map(int,readline().split())
    print(bisect.bisect(f,r)-bisect.bisect(f,l-1))

Submission status: Accepted

Solution code:
from functools import lru_cache
@lru_cache(maxsize=None)
def is_prime(x):
    if x==1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

# @lru_cache(maxsize=None)
def like2017(x):
    return is_prime(i) and is_prime((i+1)//2)
    
table=[0,0]
for i in range(2,10**5):
    table+=table[i-1]+like2017(i),
        
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    print(table[b]-table[a-1])
# print(table)

Submission status: Accepted

Solution code:
#from functools import lru_cache
#@lru_cache(maxsize=None)
def is_prime(x):
    if x==1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

# @lru_cache(maxsize=None)
def like2017(x):
    return is_prime(i) and is_prime((i+1)//2)
    
table=[0,0]
for i in range(2,10**5):
    table+=table[i-1]+like2017(i),
        
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    print(table[b]-table[a-1])
# print(table)

Submission status: Accepted

Solution code:
Q = int(input())
MAX = 10**5

def findAllOfPrime(N):
    prime = [True] * (N + 1)
    prime[0] = False
    prime[1] = False

    x = 2
    while x**2 <= N:
        if prime[x]:
            j = 2
            while x * j <= N:
                prime[x * j] = False
                j += 1
        x += 1

    return prime

prime = findAllOfPrime(MAX)
primeSum = [0] * (MAX + 1)
for x in range(1, MAX + 1):
    primeSum[x] = primeSum[x - 1]
    if prime[x] and prime[(x + 1) // 2]:
        primeSum[x] += 1
        

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

    print(primeSum[r] - primeSum[l - 1])

Submission status: Accepted

Solution code:
import math
import bisect
def prime(n):
    max=int(math.sqrt(n))
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=max:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes

Q=int(input())
l=[]
r=[]
up=0
for i in range(Q):
    a,b=map(int,input().split())
    up=max([up,a,b])
    l.append(a)
    r.append(b)

s=prime(up)
like=[]

for i in range(len(s)):
    if((s[i]+1)/2==s[bisect.bisect_left(s,(s[i]+1)/2)]):
        like.append(s[i])
        
sumli=[0]*100001
tmp=0
for i in range(2,100001):
    if(i==like[tmp]):
        sumli[i]=sumli[i-1]+1
        if(tmp<(len(like)-1)):
            tmp+=1
    else:
        sumli[i]=sumli[i-1]

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

Submission status: Accepted

Solution code:
import math
import bisect
def era(n):
    data=[i for i in range(2,n+1)]
    for d in data:
        data=[x for x in data if(x==d or x%d != 0)]
    return data
    
def prime(n):
    max=int(math.sqrt(n))
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=max:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes

Q=int(input())
l=[]
r=[]
up=0
for i in range(Q):
    a,b=map(int,input().split())
    up=max([up,a,b])
    
    l.append(a)
    r.append(b)
s=prime(up)
like=[]

for i in range(len(s)):#O(10000*log(10000))
    if((s[i]+1)/2==s[bisect.bisect_left(s,(s[i]+1)/2)]):
        like.append(s[i])
        
sumli=[0]*100001
tmp=0
for i in range(2,100001):#O(100000)
    if(i==like[tmp]):
        sumli[i]=sumli[i-1]+1
        if(tmp<(len(like)-1)):
            tmp+=1
    else:
        sumli[i]=sumli[i-1]

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

Submission status: Accepted

Solution code:
# D - 2017-like Number
from itertools import accumulate
from math import sqrt


def get_primes(n: int) -> set:
    """Return a list of prime numbers < n in O(N)."""
    if n < 2:
        return set()

    sieve = [1] * n
    for i in range(3, int(sqrt(n)) + 1, 2):
        if sieve[i]:
            sieve[i * i:: 2 * i] = [0] * ((n - i ** 2 - 1) // (2 * i) + 1)
    return {2} | {i for i in range(3, n, 2) if sieve[i]}


def main():
    Q, *LR = map(int, open(0).read().split())
    primes = get_primes(10 ** 5 + 1)
    is_2017_like = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(10 ** 5 + 1)]
    cumsum = tuple(accumulate(is_2017_like))
    ans = [cumsum[r] - cumsum[l - 1] for l, r in zip(*[iter(LR)] * 2)]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - 2017-like Number
from itertools import accumulate
from math import sqrt


def get_primes(n: int) -> set:
    """Return a list of prime numbers < n in O(N)."""
    if n < 2:
        return set()

    sieve = [1] * n
    for i in range(3, int(sqrt(n)) + 1, 2):
        if sieve[i]:
            sieve[i * i:: 2 * i] = [0] * ((n - i ** 2 - 1) // (2 * i) + 1)
    return {2} | {i for i in range(3, n, 2) if sieve[i]}


def main():
    Q, *LR = map(int, open(0).read().split())
    primes = get_primes(10 ** 5 + 1)
    is_2017_like = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(10 ** 5 + 1)]
    cumsum = tuple(accumulate(is_2017_like))
    ans = []
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(cumsum[r] - cumsum[l - 1])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    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]

primelist=get_sieve_of_eratosthenes_new(10**5)
subprimelist=[(primelist[i]+1)//2 for i in range(0,len(primelist))]
primeset=set(primelist)
subprimeset=set(subprimelist)
real=list(primeset&subprimeset)
real=[2*real[i]-1 for i in range(0,len(real))]
real.sort()

Q=int(input())
l=[0]*Q
r=[0]*Q
for i in range(0,Q):
    l[i],r[i]=map(int,input().split())
for i in range(0,Q):
    if r[i]<3 or l[i]>99877:
        print(0)
    else:
        s=0
        t=0
        start=0
        end=len(real)-1
        while end-start>1:
            test=(end+start)//2
            if real[test]>=l[i]:
                end=test
            else:
                start=test
        if real[start]>=l[i]:
            s=start
        else:
            s=end
        start=0
        end=len(real)-1
        while end-start>1:
            test=(end+start)//2
            if r[i]>=real[test]:
                start=test
            else:
                end=test
        if r[i]>=real[end]:
            t=end
        else:
            t=start
        print(t-s+1)

Submission status: Accepted

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

def jud(i):
    #iの素数判定
    num=int(i**0.5)+1
    for k in range(2,num):
        if i%k==0:
            return 0
    return 1

s=[0]*(10**5+1)
for i in range(2,10**5+1):
    if i%2==0:
        s[i]=s[i-1]
    else:
        if jud(i)*jud((i+1)//2)==1:
            s[i]=s[i-1]+1
        else:
            s[i]=s[i-1]

for k,v in l:
    ans=s[v]-s[k-1]
    print(ans)

Submission status: Accepted

Solution code:
import bisect
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]
data = get_sieve_of_eratosthenes(100001)
seta = set(data)
import collections
from collections import deque
que = deque()
for i in range(3,100001,2):
    if i in seta:
        j = (i+1)//2
        if j in seta:
            que.append(i)
listb = list(que)

Q= int(input())
l = [0] * Q
r = [0] * Q
for i in range(Q):
    laa,raa = map(int,input().split())
    l[i] = laa
    r[i] = raa
for i in range(Q):
    la = bisect.bisect_left(listb,l[i])
    ra = bisect.bisect_right(listb,r[i])
    print(ra-la)

Submission status: Accepted

Solution code:
def main():
    numbers = [0] * (10 ** 5 + 1)
    prime = [0] * (10 ** 5 + 1)
    numbers[2] = 1
    prime[2] = 1
    for i in range(3, 10 ** 5 + 1):
        if i % 2:
            is_prime = True
            j = 1
            while j * j <= i and is_prime:
                if (not i % j) and j > 1:
                    is_prime = False
                j += 1
            if is_prime:
                prime[i] = 1
            if is_prime and prime[(i + 1) // 2] and (((i + 1) // 2) % 2 or i == 3):
                numbers[i] = numbers[i - 1] + 1
            else:
                numbers[i] = numbers[i - 1]
        else:
            numbers[i] = numbers[i - 1]
    query = int(input())
    for _ in range(query):
        left, right = map(int, input().split())
        tmp = 0
        if left <= 2 <= right:
            tmp = -1
        print(numbers[right] - numbers[left - 1] + tmp)


if __name__ == '__main__':
    main()

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]


prime_num = set(get_sieve_of_eratosthenes(100000))


def isprime(x):
    return x in prime_num


ans = [0] * 100003
for x in range(2, 100000+1):
    if x % 2 == 0:
        ans[x] = ans[x - 1]
    elif isprime(x) and isprime((x+1)//2):
        ans[x] = ans[x-1] + 1
    else:
        ans[x] = ans[x-1]
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])

Submission status: Accepted

Solution code:
import math

is_primes = [False] * (10 ** 5 + 1)
def is_prime(n):
    if n == 1: return False
    if is_primes[n]:
        return True

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

    is_primes[n] = True
    return True


Q = int(input())
total = [0] * (10 ** 5 + 1)
for i in range(1, 10**5+1):
    if is_prime(i) and is_prime((i + 1) // 2):
        total[i] = total[i-1] + 1
    else:
        total[i] = total[i-1]

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

Submission status: Accepted

Solution code:
def sieve(n):
    res = list(range(n+10)) # nが小さい時よう
    res[0] = -1
    res[1] = -1
    i = 2
    while i*i<n:
        if res[i]<i:
            i += 1
            continue
        j = i*i
        while j<n:
            if res[j]==j:
                res[j] = i
            j += i
        i += 1
    return res

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

q = int(input())
res = [0]*q
for i in range(q):
    l,r = map(int, input().split())
    res[i] = acc[r+1]-acc[l]

for r in res:
    print(r)

Submission status: Accepted

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


def solve(Q: int, l: "List[int]", r: "List[int]"):
    # 10^5までの素数を予め計算しておく。
    INF = 100100
    is_prime = get_prime_numbers_array(INF)
    is_like = [0] * INF
    for i in range(INF + 1):
        if i % 2 == 0:
            continue
        if (is_prime[i] and is_prime[int((i+1)/2)]):
            is_like[i] = 1
    a = cumsum(is_like)
    for i in range(Q):
        print(a[r[i] + 1] - a[l[i]])
    return


def get_prime_numbers_array(n: int):
    """エラトステネスのふるいを用いてnまでの素数判定を行うための配列を返す

    Args:
        n ([int]): nまでの素数判定を行う
    """
    N = n + 1
    is_prime = [1] * N
    is_prime[0] = is_prime[1] = 0
    for i in range(2, N):
        if not is_prime[i]:
            continue
        for j in range(i * 2, N, i):
            is_prime[j] = 0
    return is_prime


def cumsum(data: "List[int]"):
    """dataの累積和の配列を求める。
 
    Args:
        data (List[int]): 累積和の配列を求めたい配列
    """
    a = [0] * (len(data) + 1)
    for i in range(len(data)):
        a[i + 1] = a[i] + data[i]
    return a


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    Q = int(next(tokens))  # type: int
    l = [int()] * (Q)  # type: "List[int]"
    r = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(Q, l, r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
q = int(input())
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

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

Submission status: Accepted

Solution code:
def primes(n):
    primes = []
    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(len(is_prime)):
        if is_prime[i]:
            primes.append(i)
    return is_prime


Q = int(input())

ps = primes(100000)
like_numbers = [False] * 100001
for i in range(3, 100001, 2):
    if ps[i] and ps[(i + 1) // 2]:
        like_numbers[i] = True

like_numbers_cnt = [0] * 100001

for i in range(1, 100001):
    if like_numbers[i]:
        like_numbers_cnt[i] = like_numbers_cnt[i - 1] + 1
    else:
        like_numbers_cnt[i] = like_numbers_cnt[i - 1]

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

Submission status: Accepted

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

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
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table

like = []
sieve1 = sieve(10**5)[1]
is_prime = sieve(10**5)[0]

for i in sieve1[1:]:
    if is_prime[(i+1) // 2-1]:
        like.append(i)

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

for i in like:
    li[i] = 1

for i in range(len(li) - 1):
    li[i+1] += li[i]

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