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

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

Submission status: Accepted

Solution code:
n = int(input())
"""素因数分解"""
def factrize(n):
    b = 2
    while b*b <= n:
        if n % b == 0:
            return False
        b = b+1
    return True

f = [2]

for i in range(3,10**5+2,2):
    if factrize(i):
        f.append(i)

c = []

for j in f:
    if (j + 1)//2 in f:
        c.append(j)

o = []
res = 0
for k in range(10**5+1):
    if k in c:
        res += 1
    elif c == 2017:
        res += 1
    o.append(res)
    

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

Submission status: Accepted

Solution code:
import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    prime_2007=[]
    j=0
    lr=[0]
    cnt=0

    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)

        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    
    for item in prime_list:
        if (item+1)//2 in prime_list:
            prime_2007.append(item)

    for item in prime_2007:
        lr+=[cnt]*(item - j-1)
        cnt+=1
        j=item
        lr.append(cnt)
    lr+=[cnt]*(10**5-j)
    #print(prime_2007)
    #print(lr)
    #return prime_list
    return(lr)


lrlr=get_primenumber(10**5+10)

result=[]
n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    #l=min(l,len(lrlr)-1)
    #r=min(r,len(lrlr)-1)
    #print(l,r)
    #print(len(lrlr))

    result.append(lrlr[r]-lrlr[l-1])

for item in result:
    print(item)

Submission status: Accepted

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


def is_2017(x):
    if x % 2 == 0:
        return False
    return is_p[x] and is_p[(x + 1) // 2]

def is_prime(x):
    if x == 1:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True


is_p = [False] * 100000
n_2017 = [0] * 100000

for i in range(1, 100000):
    is_p[i] = is_prime(i)

for i in range(1, 100000):
    if is_2017(i):
        n_2017[i] = n_2017[i - 1] + 1
    else:
        n_2017[i] = n_2017[i - 1]

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

Submission status: Accepted

Solution code:
m = 100010

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

a = primes(m * 2 + 100)
n = int(input())

from bisect import bisect_left
def index(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    return False

def do(x):
    if index(a, x) and index(a, (x + 1) // 2):
        return True

dat = [-1] * m
count = 0
for i in range(len(a)):
    if a[i] > m:
        break
    if do(a[i]):
        count += 1
    dat[a[i]] = count
c = -1
for i in range(m):
    if dat[i] != -1:
        c = dat[i]
    else:
        dat[i] = c
dat[0] = dat[1] = 0

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

Submission status: Accepted

Solution code:
m = 100010
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 [i for i in range(n + 1) if is_prime[i]]
a = primes(m * 2+ 100)
n = int(input())

from bisect import bisect_left
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def do(x):
    if x in a and (x+1)//2 in a:
        return True
dat = [-1] * m
count = 0
for i in range(len(a)):
    if a[i] > m:
        break
    if do(a[i]):
        count += 1
    dat[a[i]] = count
c = -1
for i in range(m):
    if dat[i] != -1:
        c = dat[i]
    else:
        dat[i] = c
dat[0] = dat[1] = 0

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

Submission status: Accepted

Solution code:
from math import sqrt

max_lr = 10 ** 5

sieve = [True] * (max_lr + 1)
sieve[0] = False
sieve[1] = False
for i in range(2, int(sqrt(max_lr)) + 1):
    if not sieve[i]:
        continue
    for j in range(i * i, max_lr + 1, i):
        sieve[j] = False

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

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

Submission status: Accepted

Solution code:
max_lr = 10 ** 5

sieve = [True] * (max_lr + 1)
sieve[0] = False
sieve[1] = False
for i in range(2, max_lr + 1):
    if not sieve[i]:
        continue
    for j in range(i * i, max_lr + 1, i):
        sieve[j] = False

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

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

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations
from itertools import accumulate
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7


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=[list(map(int,input().split())) for i in range(q)]
lst=[0]*(10**5+1)
for i in range(10**5+1):
    if i%2==1:
        if is_prime(i) and is_prime((i+1)//2):
            lst[i]+=1

lst2=[0]
lst2.extend(accumulate(lst))
# print(lst2)
for i in range(q):
    print(lst2[lr[i][1]+1]-lst2[lr[i][0]])

Submission status: Accepted

Solution code:
from itertools import accumulate

Q = int(input())
n = 10 ** 5
L = [0] * 2 + [1] * (n-1)

for i in range(int(n ** 0.5)+1):
    if L[i] == 1:
        j = 2
        while i * j <= n:
            L[i*j] = 0
            j += 1
            
T = [0] * (n+1)
for i in range(3,n):
    if L[i] == 1 and L[(i+1) // 2] == 1:
        T[i] = 1    
s = list(accumulate(T))
    
for i in range(Q):
    l, r = map(int, input().split())
    print(s[r]-s[l-1])

Submission status: Accepted

Solution code:
Q = int(input())
lr = []
maxr = 0
for i in range(Q):
    l,r = map(int,input().split())
    maxr = max(maxr,r)
    lr.append([l,r])
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(3,n + 1) if is_prime[i] and is_prime[(i+1)//2]]
prime = primes(maxr)
import bisect
for l,r in lr:
    print(bisect.bisect_right(prime,r)-bisect.bisect_right(prime,l-1))

Submission status: Accepted

Solution code:
def primes(n):
    is_prime = [True for _ in range(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

e = primes(10**5)

tc = 0
li = []

for i in range(len(e)):
    if i%2 == 0:
        li.append(tc)
    else:
        if e[i] and e[(i+1)//2]:
            tc += 1
        li.append(tc)

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

e = primes(10**5)

tc = 0
li = []

for i in range(len(e)):
    if i%2 == 0:
        li.append(tc)
    else:
        if e[i] and e[(i+1)//2]:
            tc += 1
        li.append(tc)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left

import math
n = 10**5
e = [True]*(n+1)
e[0] = False
e[1] = False
for i in range(2, int(n**0.5)+1):
    if not e[i]:
        continue
    for j in range(i*2, n+1, i):
        e[j] = False

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

for i in range(3, n+1):
    c[i] += c[i-1]

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

Submission status: Accepted

Solution code:
def prime_table(N):
    P = [False]*2+[True]*(N-1)
    for i in range(2,int(N**.5)+1):
        if P[i]: P[2*i::i] = [False]*(N//i-1)
    return P
P = prime_table(100000)
PP = [0] * 100000
for i in range(1,100000):
    PP[i] = PP[i-1] + (P[i]&P[(i+1)//2])
PP[2] = False
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(PP[r]-PP[l-1])

Submission status: Accepted

Solution code:
import bisect

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

lst = [] 
for x in range(1,10**5,2):
    if is_prime(x):
        lst.append(x)

lst_dash = []
for x in lst:
    if is_prime((x+1)//2):
        lst_dash.append(x)

q = int(input())
ans = []
for i in range(q):
    l,r = map(int,input().split())
    left = bisect.bisect_left(lst_dash, l)
    right = bisect.bisect_right(lst_dash, r)
    ans.append(right - left)

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

Submission status: Accepted

Solution code:
import math

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

# print(Q, L, R)

max_lr = 10**5

def gen_primes():
    primes = [2]
    for i in range(3, max_lr, 2):
        is_prime = True
        limit = int(math.sqrt(i)) + 1
        for p in primes:
            if p > limit:
                break
            if i % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
    # print(len(primes))
    return primes

primes = gen_primes()

def is_2017_like(n):
    m = (n + 1) // 2
    return n in primes and m in primes

A = [0]*(max_lr//2 + 1)
a = 0
for i in range(1, max_lr, 2):
    if is_2017_like(i):
        a += 1
    A[i//2 + 1] = a

for i in range(Q):
    ans = A[R[i]//2 + 1] - A[L[i]//2]
    print(ans)

Submission status: Accepted

Solution code:
n = 10**5
e = [True]*(n+1)
e[0] = False
e[1] = False
for i in range(2, int(n**0.5)+1):
    if not e[i]:
        continue
    for j in range(i*2, n+1, i):
        e[j] = False

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

for i in range(3, n+1):
    c[i] += c[i-1]

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

Submission status: Accepted

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

SIZE = 10 ** 5
P = [-1] * (SIZE + 1)
P[0], P[1] = 0, 0

for i in range(2, SIZE + 1):
  if P[i] == -1:
    P[i] = 1
    k = 2
    while i * k <= SIZE:
      P[i * k] = 0
      k += 1
      
PP = [0] * (SIZE + 1)
for i in range(3, SIZE + 1):
  if P[i] and P[(i + 1) // 2]:
    PP[i] = 1
#print(PP)

Acum = [0]
for i in range(SIZE + 1):
  Acum.append(Acum[-1] + PP[i])
#print(Acum)

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

Submission status: Accepted

Solution code:
import math

def s(number):
    if number <= 2:
        return 0
    for i in range(2,math.floor(math.sqrt(number))+1):
        if number % i == 0:
            return 0
    for i in range(2,math.floor(math.sqrt((number+1)//2))+1):
        if ((number+1)//2) % i == 0:
            return 0
    return 1

num = [s(i) for i in range(1,10 ** 5+1)]
li = [0]
for nu in num:
    li.append(li[-1]+nu)

q = int(input())

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

Submission status: Accepted

Solution code:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Submission status: Accepted

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

def lnum(n):  # Like number
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False

MAX = 10**5+10
a = [0]*MAX
for i in range(MAX):
    if lnum(i):
        a[i] = 1
    else:
        continue

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

Submission status: Accepted

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

def lnum(n):  # Like number
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False

MAX = 101010
a = [0]*MAX
for i in range(MAX):
    if lnum(i):
        a[i] = 1
    else:
        continue

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

Submission status: Accepted

Solution code:
import math

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    return 1

Q = int(input())
MAX = 10 ** 5 + 1
prime = [0] * MAX
for i in range(3, MAX):
    prime[i] = prime[i-1] + isPrime(i)
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(prime[r] - prime[l-1])
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
q=int(input())
l=[list(map(int,input().split())) for i 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 [i for i in range(n + 1) if is_prime[i]]
p=primes(10**5)
a=[0]*(10**5+1)
cnt=0
for i in range(1,10**5+1):
  if i%2==1 and i in p and (i+1)//2 in p:
    cnt+=1
  a[i]=cnt
for i in range(q):
  print(a[l[i][1]]-a[l[i][0]-1])

Submission status: Accepted

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right
def eratosthenes(N):
    # 素数判定
    flag = True
    for i in range(2, int(N**0.5) + 1):
        if N % i == 0:
            flag = False
            break
    return flag

def make_prime_nums(N):
    # Nまでの素数のリストを作成
    prime_tf = [True for _ in range(N+1)]
    prime_tf[0] = False
    prime_tf[1] = False
    for i in range(N+1):
        if prime_tf[i]:
            if eratosthenes(i):
                for j in range(i*2, N+1, i):
                    prime_tf[j] = False
    primes = [i for i in range(N+1) if prime_tf[i]]
    return primes

def make_prime_new(L):
    new_primes = []
    for l in L:
        tmp = (l+1) // 2
        if eratosthenes(tmp):
            new_primes.append(l)
    return new_primes

primes = make_prime_nums(10**5)
primes = make_prime_new(primes)[1:]
# print(primes)
N = int(input())
for _ in range(N):
    l, r = map(int, input().split())
    r += 1
    l_idx = bisect_left(primes, l)
    r_idx = bisect_left(primes, r)
    if l == r and l_idx == r_idx and l == primes[l_idx]:
        print(1)
    else:
        print(r_idx - l_idx)

Submission status: Accepted

Solution code:

def main():
    n = int(input())

    sosuu_mask = sosuu()

    r = [0 for i in range(int(1e5+1))]
    l = [0 for i in range(int(1e5+1))]
    for i in range(len(r)-2,0,-1):
        r[i] += r[i+1] + sosuu_mask[i+1]
    for i in range(1,len(l)):
        l[i] += l[i-1] + sosuu_mask[i-1]
    _all = len([s for s in sosuu_mask if s==1])
    
    # print(_all)
    # print(r[:10])
    # print(l[:10])

    for i in range(n):
        a,b = list(map(int,input().split(' ')))
        # print(list(map(int,input().split(' '))))
        print(_all-l[a]-r[b])
    return 

def sosuu():
    ret = [1 for i in range(int(1e5+1))]
    ret[0]=0
    ret[1]=0
    for i in range(2,len(ret)):
        if ret[i]==0:
            continue
        else:
            for j in range(2*i,len(ret),i):
                ret[j] = 0
    # print(ret[:54])
    ret2 = [s for s in ret]
    for i in range(len(ret)):
        if i%2==1 and ret[(i+1)//2]!=1 or i%2==0:
            ret2[i]=0
    # print(ret2[:54])
    return ret2


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    else:
        return 1

def main():
    Q = int(input())

    MAX = 10 ** 5
    prime = [0] * MAX
    for i in range(3, MAX):
        prime[i] = prime[i-1] + isPrime(i)

    for _ in range(Q):
        l, r = map(int, input().split())
        print(prime[r] - prime[l-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def isPrime(n):
    if n <= 2:
        return 0

    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    else:
        return 1

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

    MAX = 10 ** 5
    prime = [0] * MAX
    for i in range(1, MAX):
        prime[i] = prime[i-1] + isPrime(i)
    for i in lr:
        l, r = i
        if prime[l] != prime[l-1]:
            print(prime[r] - prime[l]+1)
        else:
            print(prime[r] - prime[l])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def Eratosthenes():
    num=[True for i in range(100001)]
    num[0]=False
    num[1]=False
    for i in range(2,100001):
        if num[i]:
            for j in range(2*i,100001,i):
                num[j]=False
    return num

if __name__ == '__main__':
    Q=int(input())
    Queries=[list(map(int,input().split())) for i in range(Q)]
    p_list=Eratosthenes()
    dp=[0 for _ in range(100001)]
    for i in range(3,100000):
        if p_list[i] and p_list[(i+1)//2]:
            dp[i+1]=dp[i]+1
        else:
            dp[i+1] = dp[i]
    for l,r in Queries:
        print(dp[r+1]-dp[l])

Submission status: Accepted

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

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

is_prime = eratosthenes(10**5)
a = [0 for i in range(10**5+1)]
for i in range(10**5+1):
    if i % 2 == 0:
        continue
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] = 1

b = [0]
for i in range(10**5+1):
    b.append(b[-1] + a[i])

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
Q=int(input())
lr=[list(map(int,input().split())) for _ in range(Q)]
#素数リスト
n = 100000+100
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)
#print(primes)
from bisect import bisect_left as bl
a=[0]*100001
for i in primes:
    s=bl(primes,(i+1)//2)
    if primes[s]==(i+1)//2:
        a[i]=1
#print(a)
for i in range(1,100001):
    a[i]+=a[i-1]

for i in range(Q):
    print(a[lr[i][1]]-a[lr[i][0]-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc084/tasks/abc084_d
# エラトステネスの篩を使う以外に考えられないが...
# あと高速化のために累積和も

import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def ret_erators(N: int):
    # エラトステネスの篩
    is_prime = [True] * (N + 1)

    # 0と1は素数ではない
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, int(N**0.5) + 1):
        if is_prime[i]:
            j = i * 2  # iの倍数は素数ではない
            while j < N + 1:
                is_prime[j] = False
                j += i
    return is_prime


is_prime = ret_erators(10 ** 5)

# make is_like2017
is_like = [0] * (10**5 + 1)
for x in range((10 ** 5) // 2 + 1):
    if not is_prime[x]:
        continue
    n = 2 * x - 1
    if is_prime[n]:
        is_like[n] = 1

# make accum
from itertools import accumulate
is_like_accum = [0] + list(accumulate(is_like))

Q = int(input())
L, R = read_col(Q, 2)


for l, r in zip(L, R):
    print(is_like_accum[r + 1] - is_like_accum[l])

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


# 累積和
counts = [0]
buf = 0
for i in range(1, 10**5 + 2):
    if i % 2 == 0:
        counts.append(buf)
        continue
    
    judge1 = is_prime(i)
    judge2 = is_prime((i + 1) // 2)
    
    if judge1 and judge2:
        buf += 1
    
    counts.append(buf)


# 入力
Q = int(input())

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

Submission status: Accepted

Solution code:
prime = [3, 5]
for i in range(13, 102010, 12):
  r = int(i**(1/2))
  p = 0
  for j in range(2, r+1):
    if i % j == 0:
      p = 1
      break
  a = (i+1)//2
  r = int(a**(1/2))
  for j in range(2, r+1):
    if a % j == 0:
      p = 1
      break
  if p == 0:
    prime.append(i)
LL = []
j = 0
for i in range(100001):
  if i >= prime[j]:
    j += 1
  LL.append(j)

Q = int(input())
for i in range(Q):
  L = list(map(int, input().split()))
  L[0] -= 1
  print(LL[L[1]] - LL[L[0]])

Submission status: Accepted

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right
def check(x):
    flag = True
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            flag = False
            break
    return flag

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]]
def primes_plus(l):
    # l: 素数の配列
    L = []
    for p in l:
        if check((p+1)//2):
            L.append(p)
    return L
l_primes = primes(10**6)
l_primes = primes_plus(l_primes)[1:]
# print(len(l_primes))
Q = int(input())
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    r += 1
    l_idx = bisect_left(l_primes, l)
    r_idx = bisect_left(l_primes, r)
    # print(l_idx, r_idx)
    if l == r and l_idx == r_idx and l == l_primes[l_idx]:
        print(1)
    else:
        print(r_idx - l_idx)
# print(l_primes)

Submission status: Accepted

Solution code:
from itertools import accumulate

def eratosthenes(mx):
    array = [1 for _ in range(mx)]
    array[0] = array[1] = 0
    for i in range(4, mx, 2):
        array[i] = 0
    for i in range(3, mx, 2):
        if not array[i]:
            continue
        for j in range(i+i, mx, i):
            array[j] = 0
    return array

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

mx = max(r)
array = eratosthenes(mx + 1)
prime = [1 if i % 2 == 1 and array[i] and array[(i+1) // 2] else 0 for i in range(mx + 1)]
acc = list(accumulate(prime))
# print(acc[:20])

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

Submission status: Accepted

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

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
    
MAX = 10 ** 5
a = [0] * MAX
sum = [0] * (MAX + 1)
for i in range(MAX):
    if i % 2 == 0:
        continue
    if is_prime(i) and is_prime((i+1)/2):
        a[i] = 1;
        
for i in range(MAX):
    sum[i+1] = sum[i] + a[i]

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

Submission status: Accepted

Solution code:
from itertools import accumulate
# エラトステネスの篩
# is_prime := 1~nが素数か否か
# table := 2~nのうち素数
def sieve(n):
    is_prime = [True for _ in range(n)]
    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


Q = int(input())
L = [0]*Q
R = [0]*Q

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

max_R = max(R)
is_prime, table = sieve(max_R)

check = [0]*(max_R + 1)
for i in range(0, max_R + 1):
    if (i % 2 == 1):
        if (is_prime[i-1] and is_prime[(i+1)//2-1]):
            check[i] = 1

# 累積和
check = [0] + check
check = list(accumulate(check))

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

Submission status: Accepted

Solution code:
def is_prime(n):
    '''
    素数判定する
    '''
    if n == 1:
        return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True


Q = int(input())
prime_list = [False] * 100001
L = []
R = []
for _ in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
a = [0] * 100001
prime_list[2] = True
for i in range(1, 100001):
    prime_list[i] = is_prime(i)
    if prime_list[i] and prime_list[(i+1)//2]:
        a[i] = a[i-1] + 1
    else:
        a[i] = a[i-1]
for i in range(Q):
    ans = a[R[i]] - a[L[i]-1]
    print(ans)