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:
# O(nloglogn) https://mathtrain.jp/eratosthenes
def sieve(n):
	s = [True] * n
	s[0] = s[1] = False
	for x in range(2, int(n ** 0.5) + 1):
		if s[x]:
			for i in range(2 * x, n, x):
				s[i] = False
	return s

is_prime = sieve(10 ** 5 + 1)
is_like2017 = [False] * (10 ** 5 + 1)
for i in range(10**5 + 1):
	if is_prime[i] and is_prime[(i + 1) // 2]:
		is_like2017[i] = True

# 区間内のlike2017を求める
# 累積和を用いて高速化
c = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
	if is_like2017[i]:
		c[i] = c[i - 1] + 1
	else:
		c[i] = c[i-1]

# 出力
q = int(input())

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

Submission status: Accepted

Solution code:
import itertools
n = int(input())
lr = [[int(i) for i in input().split()] for _ in range(n)]
max = 101010
p = [1]*max
p[0] = 0
p[1] = 0
for i in range(2, max):
    if p[i] == 1:
        for j in range(int(i*2), max, i):
            p[j] = 0
a = [0]*(max+1)
for i in range(1, max, 2):
    if p[i] == p[(i+1)//2] == 1:
        a[i+1] = 1
a = list(itertools.accumulate(a))
for l, r in lr:
    print(a[r+1] - a[l])

Submission status: Accepted

Solution code:
import sys
import numpy as np
from itertools import accumulate


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


sys.setrecursionlimit(10 ** 9)


def main():
    def make_prime(U):
        is_prime = np.zeros(U, np.bool)
        is_prime[2] = 1
        is_prime[3::2] = 1
        M = int(U ** 0.5) + 1
        for p in range(3, M, 2):
            if is_prime[p]:
                is_prime[p * p :: p + p] = 0
        return is_prime

    primes = make_prime(10 ** 5 + 1)
    check = np.where(primes == True, 1, 0)
    for i in range(1, 10 ** 5 + 1):
        if i % 2 == 1:
            if primes[i]:
                if not primes[(i + 1) // 2]:
                    check[i] = 0
        else:
            continue
    check[2] = 0
    check = list(accumulate(check))
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        print(check[r] - check[l - 1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

q = int(input())
list_Q = [ list(map(int,input().split(" "))) for i in range(q)]

num = pow(10, 5)
list_PRE = [0]*(2*num+10)
list_PRE[2] = 1
for i in range(1, 2*num+10, 2):
    if len(prime_factorize(i)) == 1:
        list_PRE[i] = 1

list_2017 = [0]*(2*num+10)
for i in range(1, num+1, 2):
    if list_PRE[i] == 1 and list_PRE[(i+1)//2] == 1:
        list_2017[i] = 1

list_ANS = []
cnt = 0
for i in list_2017:
    if i == 1:
        cnt += 1
        list_ANS.append(cnt)
    else:
        list_ANS.append(cnt)

for i, j in list_Q:
    print(list_ANS[j]-list_ANS[i-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def is_prime(n: int):
    if n == 1:
        return False
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True


def solve(Q: int, l: "List[int]", r: "List[int]"):
    pm = [is_prime(n) for n in range(1, 100001, 2)]
    tm = [
        pm[(n - 1) // 2] and (
            n == 3 or
            ((n + 1) // 2 % 2 == 1 and pm[((n + 1) // 2 - 1) // 2])
        )
        for n in range(1, 100001, 2)
    ]
    acc = [0] * (len(tm) + 1)
    for i in range(len(tm)):
        acc[i + 1] = acc[i] + int(tm[i])
    for li, ri in zip(l, r):
        print(acc[(ri - 1) // 2 + 1] - acc[(li - 1) // 2])


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:
import itertools
n = int(input())
lr = [[int(i) for i in input().split()] for _ in range(n)]
m = 101010
p = [1]*m
p[0] = p[1] = 0
for i in range(2, m):
    if p[i] == 0: continue
    else:
        for j in range(2*i, m, i):
            p[j] = 0
a = [0]*m
for i in range(1, m, 2):
    if p[i] == p[(i+1)//2] == 1: a[i] = 1
a = list(itertools.accumulate(a))
for l, r in lr:
    print(a[r] - a[l-1])

Submission status: Accepted

Solution code:
import math

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

prime=[]
for n in range(2, 10**5+1):
    for i in range(2, math.floor(math.sqrt(n)) + 1):
        if n % i == 0:
            break
    else:
        prime.append(n)
#print(prime)



like2017=[0]*(10**5+1)
for p in prime:
    if (p+1)//2 in prime:
        like2017[p]=1
#print(like2017)

cumulative=[0]
for i in range(10**5):
    cumulative.append(like2017[i]+cumulative[i])
#print(cumulative)

for q in lr:
    l, r = q
    print(cumulative[r+1]-cumulative[l])

Submission status: Accepted

Solution code:
import numpy as np

Q = int(input())
q = list()
n = 10 ** 5 + 1
for _ in range(Q):
    l, r = map(int, input().split())
    q.append((l, r))

# エラトステネスのふるい
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

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

ans = np.cumsum(N)
for l, r in q:
    print(ans[r] - ans[l - 1])

Submission status: Accepted

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

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

Sum = [0] * (MAX + 1)
for i in range(MAX):
    Sum[i+1] = Sum[i] + Like[i]

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

Submission status: Accepted

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

q = int(input())

def eratosthenes2(limit):
    is_prime = [1] * (limit + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]==0:
            continue
        for j in range(i * 2, limit + 1, i):
            is_prime[j] = 0
    return is_prime

limit = 10**5

is_prime = eratosthenes2(limit)
prime_list = [i for i in range(limit + 1) if is_prime[i]]

like_2017=[0]*limit

for p in prime_list:
    if is_prime[(p+1)//2]==1:
        like_2017[p] = 1

from itertools import accumulate
B = [0] + like_2017
B = list(accumulate(B))

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

print(*ans,sep='\n')

Submission status: Accepted

Solution code:
def resolve():
    Q = int(input())
    # pair = [tuple(map(int, input().split())) for _ in range(Q)]

    def get_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[i] for i in range(n + 1)]

    primes = get_primes(10**5+1)
    cum = [0] * (10**5 + 1)
    for i in range(2, 10**5+1):
        cum[i] += cum[i-1]
        if i % 2 and primes[i] and primes[(i+1)//2]:
            cum[i] += 1
    for _ in range(Q):
        l, r = map(int, input().split())
        print(cum[r] - cum[l-1])
resolve()

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
N = 100010
primes = []
is_prime = [True]*N
for i in range(2,N):
    if is_prime[i]:
        primes.append(i)
        j = 2
        while i*j < N:
            is_prime[i*j] = False
            j += 1


# -------------------------------------------------------------
# main
# -------------------------------------------------------------

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

# 2017数の判定リストを作る
Ans = [0]*N
for p in primes:
    if p==2:
        continue
    # pは素数であるので、(p+1)//2が素数であれば 2017数
    if (p+1)//2 in primes:
        Ans[p] = 1

# 範囲計算なので累積和
for i in range(1,N):
    Ans[i] += Ans[i-1]

# クエリを処理
for l,r in LR:
    print(Ans[r] - Ans[l-1])

Submission status: Accepted

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


def IsPrime(x):
    if x == 2:
        return True
    elif x % 2 == 0:
        return False
    else:
        for i in range(3, int(x**0.5)+2, 2):
            if x%i == 0:
                return False
        else:
            return True
        

like = [False] * (10**5+1)
for i in range(3, 10**5, 2):
    like[i] = IsPrime(i) and IsPrime((i+1)//2)

ans = [0]*(10**5+1)
tmp = 0
for i in range(10**5+1):
    if like[i] == True:
        tmp += 1
    ans[i] = tmp

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

Submission status: Accepted

Solution code:

import math

def submit():
    n_max = 10**5

    # n_maxまでの素数を数える
    is_prime = {x: True for x in range(1, n_max + 1)}
    is_prime[1] = False
    for x in range(2, math.ceil(math.sqrt(n_max)) + 1):
        if is_prime[x]:
            y = 2 * x
            while y <= n_max:
                is_prime[y] = False
                y += x

    like2017 = {}
    for x in range(1, n_max + 1):
        like2017[x] = x % 2 and is_prime[x] and is_prime[(x + 1) // 2]

    # xまでの2017に似た数の個数を覚えておく
    accumulation = {0: 0}
    for x in range(1, n_max + 1):
        accumulation[x] = accumulation[x - 1] + like2017[x]
    
    # クエリを処理する
    q = int(input())
    queries = []
    for _ in range(q):
        queries.append(list(map(int, input().split())))
        
    for l, r in queries:
        print(accumulation[r] - accumulation[l - 1])
    
submit()

Submission status: Accepted

Solution code:
q=int(input())
s=set()
arr=[0]*(10**5+1)
for i in range(2,10**5+1):
  if arr[i]==0:
    s.add(i)
    for j in range(i,10**5+1,i):
      arr[j]+=1
cnt=[0]*(10**5+1)
for i in range(10**5+1):
  if i in s and (i+1)//2 in s:
    cnt[i]=1
for i in range(10**5):
  cnt[i+1]+=cnt[i]
for _ in range(q):
  l,r=map(int,input().split())
  print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
b = [0,0,0]
def judge(n):
    if  n!= 1 and all(n%i != 0 for i in range(2,round(n**(1/2) +1))):
        return True
    else:
        return False
for i in range(3,10**5):
    if judge(i) and judge((i+1)/2):
        b.append(1)
    else:
        b.append(0)
cnt = [0]*(10**5)
for i in range(1,10**5):
    cnt[i] = cnt[i-1] + b[i]
for i in range(n):
    ans = cnt[a[i][1]] - cnt[a[i][0]-1]
    print(ans)

Submission status: Accepted

Solution code:
Q=int(input())
prime = [1]*(10**5+1)
prime[0],prime[1]=0,0
for i in range(2,int(pow(10**5,0.5)+3)):
    if not prime[i]:
        continue
    for j in range(i*2,10**5+1,i):
        prime[j]=0
near_2017 = [1]*(10**5+1)
near_2017[0:3]=[0,0,0]
for i in range(3,10**5+1):
    if prime[i] and prime[(i+1)//2]:
        near_2017[i]=near_2017[i-1]+1
    else:
        near_2017[i]=near_2017[i-1]
for i in range(Q):
    l,r=map(int,input().split(' '))
    print(near_2017[r]-near_2017[l-1])

Submission status: Accepted

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

def era(n): #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(2*i, n+1, i):
            is_prime[j] = False
    
    return [i for i in range(n+1) if is_prime[i]]

p = era(10**5+100)
s = set(p)
is_like = [0]*(10**5+100)

for i in range(len(is_like)):
    if i in s and (i+1)//2 in s:
        is_like[i] = 1

acc = [0]

for i in range(len(is_like)):
    acc.append(acc[-1]+is_like[i])

Q = int(input())

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

Submission status: Accepted

Solution code:
q = int(input())
n = 10**5+1
p = [0]*n
p[2] = 1
for i in range(3,10**5+1):
  prime = 1
  for j in range(2, int(i**0.5)+1):
    if i%j==0:
      prime = 0
      break
  if prime:
    p[i] = 1

like2017 = [1 if p[i] and p[(i+1)//2] else 0 for i in range(n)]
cnter = [0]*n
for i in range(1,n):
  cnter[i] = cnter[i-1]+ like2017[i]

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

Submission status: Accepted

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

import sys

def main():
    is_prime = sieve(10 ** 5 + 1)
    is_like2017 = [(is_prime[i] and is_prime[(i + 1) // 2]) for i in range(10 ** 5 + 1)]
    counter = [0]
    for i in range(1, 10 ** 5 + 1):
        counter.append(counter[-1] + (1 if is_like2017[i] else 0))

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


# O(nloglogn) https://mathtrain.jp/eratosthenes
def sieve(n):  # exclusive
    s = [True] * n
    s[0] = s[1] = False
    for x in range(2, int(n**0.5) + 1):
        if s[x]:
            for i in range(2 * x, n, x):
                s[i] = False
    return s

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    is_prime = sieve(10 ** 5 + 1)
    is_like2017 = [(is_prime[i] and is_prime[(i + 1) // 2]) for i in range(10 ** 5 + 1)]
    counter = [0]
    for i in range(1, 10 ** 5 + 1):
        counter.append(counter[-1] + (1 if is_like2017[i] else 0))

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


# O(nloglogn) https://mathtrain.jp/eratosthenes
def sieve(n):  # exclusive
    s = [True] * n
    s[0] = s[1] = False
    for x in range(2, int(n**0.5) + 1):
        if s[x]:
            for i in range(2 * x, n, x):
                s[i] = False
    return s

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - 2017-like Number
# https://atcoder.jp/contests/abc084/tasks/abc084_d

counts = []
counts.append(0)
counts.append(0)
counts.append(0)

prime = []

is_prime = []
is_prime.append(False)
is_prime.append(False)

def sieve(r):
    for i in range(2, r + 1):
        is_prime.append(True)

    for i in range(2, r + 1):
        if is_prime[i]:
            prime.append(i)

            j = 2 * i
            while j <= r:
                is_prime[j] = False
                j = j + i

def calc_like_number_count(r):
    for i in range(3, r + 1):
        if i % 2 == 1 and is_prime[i] and is_prime[(i + 1) // 2]:
            counts.append(1)
        else:
            counts.append(0)
    
    for i in range(3, r + 1):
        counts[i] = counts[i] + counts[i - 1]


def main():
    Q = int(input())
    querys = []
    max_r = 0
    for i in range(Q):
        l, r = map(int, input().split())
        querys.append((l, r))
        if max_r < r:
            max_r = r

    sieve(max_r)
    calc_like_number_count(max_r)

    for l, r in querys:
        print(counts[r] - counts[l - 1])
    
main()

Submission status: Accepted

Solution code:
import math
def using_sqrt(limit):
    n = 0
    primes = set()
    for k in range(2, limit+1):
        factor = 0
        
        # 2以外の偶数は素数ではないので無視する
        if k % 2 == 0 and k != 2:
            continue
        
        # 繰り返しの上限を対象の平方根にする
        for divisor in range(2, math.floor(math.sqrt(k))+1):
            if k % divisor == 0:
                factor += 1
                
        if factor == 0:
            primes.add(k)
            
    return primes

primes = using_sqrt(10**5+1)

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

Submission status: Accepted

Solution code:
import math
Q = int(input())
rui = [0]*50000
def sosuu(n):
    for i in range(2,1+int(math.sqrt(n))):
        if n % i == 0:
            return 0
    return 1
for i in range(1,50000):
    n = i*2 + 1
    han = 0
    rui[i] = rui[i-1] + min(sosuu(n),sosuu((n+1)/2))
for i in range(Q):
    l,r = [int(x) for x in input().split()]
    l2 = (l-1) // 2
    r2 = (r-1) // 2
    if l2 != 0:
        print(rui[r2] - rui [l2-1])
    else:
        print(rui[r2])

Submission status: Accepted

Solution code:
from math import ceil, sqrt
from itertools import accumulate
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def eratosthenes(n):
    p = []         # n以下の素数リスト
    t = [-1] * n   # t_iの素因数の内最小のもの
    t[0] = 0
    t[1] = 0

    for i in range(2, ceil(sqrt(n))):
        if t[i] == -1:
            p.append(i)
            #t[i] = i
            for j in range(2*i, n, i):
                if t[j] == -1:
                    t[j] = i
 
    for j in range(i+1, n):
        if t[j] == -1:
            p.append(j)
            #t[j] = j
 
    return p, t
 

def main():
    Q,*lr = map(int, read().split())

    P, T = eratosthenes(10**5+5)
    table2017 = [0] * (10**5+5)
    for p in P:
        if T[(p+1)//2] == -1:
            table2017[p] = 1
    acc = list(accumulate(table2017))

    for l, r in zip(*[iter(lr)]*2):
        print(acc[r] - acc[l-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
size = 10 ** 5
is_prime = [True] * size
is_prime[0] = False
for i in range(1, int(size ** 0.5)):
  if not is_prime[i]:
    continue
  for j in range(2 * i + 1, size, i + 1):
    is_prime[j] = False
counts = [0] * size
for i in range(size):
  if is_prime[i] and is_prime[(i + 1) // 2]:
    counts[i] = counts[i - 1] + 1
  else:
    counts[i] = counts[i - 1]

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

Submission status: Accepted

Solution code:

q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]
#nの素数判定
def is_prime(n):
    if n == 1:
        return 0
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return 0
    return 1

m = 0
for l, r in lr:
    m = max(l, r, m)
prime_count = [0, 0]
for i in range(2, m+1):
    prime_count += [is_prime(i)]
similar = [0]*(m+1)
for i in range(3, m+1):
    if prime_count[i] == 1 and prime_count[(i+1)//2] == 1:
        similar[i] = 1
for i in range(m):
    similar[i+1] = similar[i+1] + similar[i]

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

Submission status: Accepted

Solution code:
def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime

lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(input())
lis = set(lis)-{0}
c = [0]*(10**5+1)
for i in range(10**5):
    if i+1 in lis:
        c[i+1] = c[i]+1
    else:
        c[i+1] =c[i]
c = tuple(c)
for _ in range(Q):
    l,r = map(int,input().split())
    tmp = c[r]-c[l-1]
    print(tmp)

Submission status: Accepted

Solution code:
def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime
from bisect import bisect_left as bl
from bisect import bisect_right as br
lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(input())
lis = set(lis)-{0}
lis = sorted(tuple(lis))
for _ in range(Q):
    l,r = map(int,input().split())
    t = bl(lis,l)
    s = br(lis,r)
    tmp = s-t
    print(tmp)

Submission status: Accepted

Solution code:
from itertools import accumulate

def get_prime_number_list(N):
    # N以下の素数のリストを返す
    primes = [2]
    limit = int(N**0.5)
    data = [i+1 for i in range(2, N, 2)]
    while 1:
        p = data[0]
        if limit <= p:
            return primes + data
        primes.append(p)
        data = [e for e in data if e%p != 0]

def main():
    Q=int(input())
    primes = get_prime_number_list(10**5)
    prime_lst = [0]*(10**5+10)
    tmp = [0]*(10**5+10)
    for prime in primes:
        prime_lst[prime] = 1
    for i in range(3, 10**5+10, 2):
        if prime_lst[i] and prime_lst[(i+1)//2]:
            tmp[i] = 1
    ans = list(accumulate(tmp))
    l_r = []
    for _ in range(Q):
        l_r.append(map(int,input().split()))
    for l,r in l_r:
        print(ans[r] - ans[l-1])

main()

Submission status: Accepted

Solution code:
import math

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

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

primes = sieve(100000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

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

Submission status: Accepted

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return set([i for i in range(n + 1) if is_prime[i]])
 
p_set = primes(10 ** 5)
sum_list = [0] * ((10 ** 5) + 1)
 
for i in range(len(sum_list) - 1):
    ret = 0
    if (i+1) in p_set and ((i+2) // 2) in p_set:
        ret = 1
    else:
        ret = 0
    sum_list[i+1] = sum_list[i] + ret

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

Submission status: Accepted

Solution code:
lim = 10 ** 5

primes = [True] * (lim + 1)
primes[0], primes[1] = False, False
for i in range(2, int(lim ** 0.5) + 1):
    if primes[i]:
        for j in range(i * 2, lim, i):
            primes[j] = False

like = [False] * (lim + 1)
for i in range(1, lim + 1):
    if primes[i] and primes[(i + 1) // 2]:
        like[i] = True

cumsum = [0] * (lim + 1)
for i in range(1, lim + 1):
    if like[i]:
        cumsum[i] = cumsum[i - 1] + 1
    else:
        cumsum[i] = cumsum[i - 1]

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

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left


size = 10 ** 5 + 1

is_prime = [True] * size
is_prime[0] = is_prime[1] = False

# √size まで
for i in range(2, 317):
  j = 2 * i
  while j < size:
    is_prime[j] = False
    j += i

# 先に like_numbers のテーブルを作っておく    
like_numbers = [
  i 
  for i, x in enumerate(is_prime)
  if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2]
]

Q = int(input())

for _ in range(Q):
  l, r = map(int, input().split())
  # l から r まで探索してると 10^5 かかって間に合わないので二分探索を行う
  print(bisect(like_numbers, r) - bisect_left(like_numbers, l))

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left


size = 10 ** 5 + 1

is_prime = [True] * size
is_prime[0] = is_prime[1] = False

# √size まで
for i in range(2, 317):
  j = 2 * i
  while j < size:
    is_prime[j] = False
    j += i

like_numbers = [
  i 
  for i, x in enumerate(is_prime)
  if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2]
]

Q = int(input())

# print(like_numbers[:20])

for _ in range(Q):
  l, r = map(int, input().split())
  if l == r:
    print(1 if l in like_numbers else 0)
  else:
  	print(bisect(like_numbers, r) - bisect_left(like_numbers, l))

Submission status: Accepted

Solution code:
thres = 10 ** 5

isPrime = [True] * (thres + 5)
isPrime[0] = isPrime[1] = False
idx = 2
while (idx * idx) <= thres:
    if isPrime[idx] is True:
        for k in range(idx + idx, thres, idx):
            isPrime[k] = False
    idx += 1

isLike = [False] * (thres + 5)
isLike[0] = False
for i in range(1, thres + 1):
    if isPrime[i] is True and isPrime[(i + 1) // 2] is True:
        isLike[i] = True

cum = [0] * (thres + 5)
cum[0] = cum[1] = 0
for i in range(1, thres + 1):
    if isLike[i] is True:
        cum[i] = cum[i - 1] + 1
    else:
        cum[i] = cum[i - 1]

q = int(input())

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

Submission status: Accepted

Solution code:
def check(i):
    num=int(i**0.5)
    if i==1:return 0
    if i==2:return 1
    for j in range(2,num+1):
        if i%j==0:break

    else:return 1
    return 0
q=int(input())
lr=[list(map(int,input().split())) for i in range(q)]

L=[0]*(10**5+1)#0~100000
for i in range(10**5+1):
    if i%2==0:
        L[i]=L[i-1]
    else:
        L[i]=L[i-1]+check(i)*check((i+1)//2)

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

Submission status: Accepted

Solution code:
import math

q=int(input())
N=[0]*(10**5+1)
N[3]=1
N[2]=1
S=[]

for i in range(5,10**5+1,2):
    flag=True
    for j in range(3,int(math.sqrt(i))+1,2):
        if i%j==0:
            flag=False
            break
    if flag:
        N[i]=1

X=[0]*(10**5+1)
X[2]=1
cnt=0
for i in range(3,10**5+1,2):
    if N[i]==1 and N[(i+1)//2]==1:
        cnt+=1
    X[i]=cnt
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    print(X[r]-X[l-2])

Submission status: Accepted

Solution code:
import math

q=int(input())
N=[0]*(10**5+1)
N[3]=1
N[2]=1
S=[]

for i in range(5,10**5+1,2):
    flag=True
    for j in range(3,int(math.sqrt(i))+1,2):
        if i%j==0:
            flag=False
            break
    if flag:
        N[i]=1

X=[0]*(10**5+1)
X[2]=1
cnt=0
for i in range(3,10**5+1,2):
    if N[i]==1 and N[(i+1)//2]==1:
        cnt+=1
    X[i]=cnt
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    Q.append([l,r])

for l,r in Q:
    print(X[r]-X[l-2])

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


q = int(input())
lr = []
rmax = 0
for _ in range(q):
    l, r = map(int, input().split())
    lr.append([l, r])
    rmax = max(rmax, r)

csum = [0]
for i in range(1, rmax+1):
    if is_prime(i) and (i+1) % 2 == 0 and is_prime((i+1)//2):
        csum.append(csum[i-1]+1)
    else:
        csum.append(csum[i-1])

#print(csum)
for i in range(q):
    if lr[i][1] == lr[i][0]:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        #print(csum[lr[i][1]]-csum[lr[i][0]], lr[i][0],lr[i][1], csum[lr[i][0]], csum[lr[i][1]])
    else:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        #print(csum[lr[i][1]]-csum[lr[i][0]-1], lr[i][0],lr[i][1], csum[lr[i][0]], csum[lr[i][1]])

Submission status: Accepted

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
n=int(input())
prime=primes((10**5)+1)
memo=[0]*((10**5)+1)

for i in range(1,(10**5)+1,2):
    if prime[i]==True and prime[(i+1)//2]==True:
        memo[i]=1
      
from itertools import accumulate  
ac=list(accumulate(memo))
#print(ac)

for i in range(n):
    l,r=map(int,input().split())
    if l!=0:
        print(ac[r]-ac[l-1])
    elif l==0:
        print(ac[r])

Submission status: Accepted

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

def is_prime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x%2 == 0:
        return False
    for i in range(3, min(int(x**0.5)+5, x), 2):
        if x%i == 0:
            return False
    return True

for i in range(1, len(ans)):
    if is_prime(i) and is_prime((i+1)//2):
        ans[i] += 1
    ans[i] += ans[i-1]

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

Submission status: Accepted

Solution code:
import sys


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

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

    return is_prime


N = 10 ** 5
isPrime = sieve(N)
is2017 = [0] * (N + 1)
for i in range(N + 1):
    if 2 * i - 1 <= N and isPrime[i] and isPrime[2 * i - 1]:
        is2017[2 * i - 1] = 1

S = [0] * (N + 1)
for i in range(N):
    S[i + 1] = S[i] + is2017[i + 1]

Q = int(input())
for s in sys.stdin.readlines():
    l, r = map(int, s.split())
    print(S[r] - S[l - 1])

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N
B = [0]*N
for i in range(N):
  A[i],B[i] = map(int, input().split())
  
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

P,Q = [0]*10**5,[0]*10**5
P[2]=True
Q[1]=0
for i in range(3,10**5,2):
  P[i] = is_prime(i)
  if P[i]==True and P[(i+1)//2]==True:
    Q[i]=Q[i-2]+1
  else:
    Q[i]=Q[i-2]
    
ans = []
for i in range(N):
  if A[i]==1:
    ans.append(Q[B[i]])
  else:
    ans.append(Q[B[i]]-Q[A[i]-2])

print(*ans,sep='\n')