Problem:


Score : 400 points

Problem Statement

We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Sample Input 1

1
3 7

Sample Output 1

2

3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.

5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.

7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.

Thus, the response to the first query should be 2.

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

6
1 53
13 91
37 55
19 51
73 91
13 49

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Accepted

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

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

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

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

for x in lst:
    print(cum[x[1]] - cum[x[0]-1])

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
Q = int(input())
prime = set()
cuml = []
count = 0
for i in range(1,100000,2):
    if len(make_divisors(i)) == 2:
        if len(make_divisors((i+1)//2)) == 2:
            prime.add(i)
for i in range(1,100000,2):
    if i in prime:
        count += 1
    cuml.append(count)
for i in range(Q):
    l,r = (int(x) for x in input().split())
    if l > 1:
        print(cuml[(r-1)//2]-cuml[(l-3)//2])
    else:
        print(cuml[(r-1)//2])

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    prime = [1] * (10**5+1)
    prime[1] = 0
    for i in range(2, 10**5+1):
        if i:
            for j in range(2, 10**5+1):
                if i*j <= 10**5:
                    prime[i*j] = 0
                else:
                    break

    cs = [0] * (10**5+1)
    for i in range(1, 10**5+1):
        cs[i] = cs[i-1] + (i&1 and prime[i] and prime[(i+1)//2])
    for _ in range(int(input())):
        l, r = map(int, input().split())
        print(cs[r] - cs[l-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

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

def main():
    n = 10**5
    p = [i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0 for i in range(n + 1)]
    p[1] = False
    p[2] = p[3] = p[5] = p[7] = True
    for pi in range(3, int(n ** 0.5) + 1, 2):
        if not p[pi]:
            continue
        for i in range(pi ** 2, n + 1, pi):
            p[i] = False
    like = [i % 2 == 1 and p[i] and p[(i + 1) // 2] for i in range(n)]
    a = [0] + list(accumulate(like))[1:]
    for _ in range(int(read())):
        l, r = map(int, read().split())
        print(a[r] - a[l - 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
Q = int(input())
maxn = 10 ** 5
intn = [True] * (maxn+1)
intn[0] = False
intn[1] = False
prime = list()
like2017 = list()
for n in range(2, maxn+1):
  if(intn[n] == False):
    continue
  prime.append(n)
  tmp = n
  while(tmp <= maxn):
    intn[tmp] = False
    tmp += n

for i in prime:
  q = (i+1)//2
  q_loc = bisect.bisect_left(prime, q)
  if(prime[q_loc] == q):
    like2017.append(i)

for i in range(Q):
  l, r = map(int, input().split())
  ln = bisect.bisect_left(like2017, l)
  rn = bisect.bisect_right(like2017, r)
  print(rn-ln)

Submission status: Accepted

Solution code:
# import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize

# ===CODE===
q = int(input())

condition = 10 ** 5

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

kodoku = {2}
kodoku_2 = [2]

for i in range(3, condition + 5, 2):
    lim = i ** (1 / 2)
    flg = True
    for div in kodoku_2:
        if div > lim:
            break
        if i % div == 0:
            flg = False
            break

    if flg:
        kodoku.add(i)
        kodoku_2.append(i)

ruisekiwa = [0] * (condition + 5)

for i in range(3, condition + 5):
    ruisekiwa[i] = ruisekiwa[i - 1]
    if i in kodoku and (i + 1) // 2 in kodoku:
        ruisekiwa[i] += 1

for l, r in data:
    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 1)]
    print(ans)

Submission status: Accepted

Solution code:
# import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize

# ===CODE===
q = int(input())

condition = 10 ** 5

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

kodoku = {2}

for i in range(3, condition + 5, 2):
    lim = i ** (1 / 2)
    flg = True
    for j in range(2, int(lim)+1):
        # if div > lim:
        #     break
        if i % j == 0:
            flg = False
            break

    if flg:
        kodoku.add(i)

ruisekiwa = [0] * (condition + 5)

for i in range(3, condition + 5):
    ruisekiwa[i] = ruisekiwa[i - 1]
    if i in kodoku and (i + 1) // 2 in kodoku:
        ruisekiwa[i] += 1

for l, r in data:
    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 1)]
    print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right

def check_prime(x):
  p= int(x**0.5)
  for i in range(2,p+1):
    if x%i==0:
      return False
  else:
    return True
  
prime=[2]
like=[]
for i in range(3,100001,2):
  if check_prime(i):
    prime.append(i)
    if (i+1)//2 in prime:
      like.append(i)
      
#print(like)

Q=int(input())
l=[0]*Q
r=[0]*Q
for i in range(Q):
  l[i],r[i]= map(int,input().split())
  s=bisect_left(like,l[i])
  t=bisect_right(like,r[i])  
  print(t-s)

Submission status: Accepted

Solution code:
from collections import defaultdict
Q = int(input())
l_list = list()
r_list = list()
for _ in range(Q):
    left, right = list(map(int, input().split(' ')))
    l_list.append(left)
    r_list.append(right)
MAX_N = max(r_list)
# Make number dict for check prime or not
prime_list = list(range(2, MAX_N + 1))
prime_index = 0
n = prime_list[prime_index]
while n**2 <= MAX_N:
    prime_list = list(filter(lambda x: x == n or x % n != 0, prime_list))
    prime_index += 1
    n = prime_list[prime_index]
prime_dict = defaultdict(int)
for p in prime_list:
    prime_dict[p] = 1
# Calculate number of 2017-like-numbers.
sum_dict = defaultdict(int)
for n in range(MAX_N + 1):
    sum_dict[n] += sum_dict[n - 1]
    if n % 2 == 0:
        continue
    nn = (n + 1) // 2
    if prime_dict[n] == 1 and prime_dict[nn] == 1:
        # `n` and `nn` are 2017-like
        sum_dict[n] += 1
# Answer all queries
for left, right in zip(l_list, r_list):
    print(sum_dict[right] - sum_dict[left - 1])

Submission status: Accepted

Solution code:
import math
num = 100000
s = set([i for i in range(2,num+1)])
p = set()
mi = 0
while mi<=math.sqrt(num):
    mi = min(s)
    t = set([i*mi for i in range(1,num//mi+1)])
    p.add(mi)
    s-=t
p = p|s
p2 = set([i for i in p if (i+1)//2 in p])
c = 0
x = [0]*100001
for i in range(1,num+1):
    if i in p2:
        c+=1
    x[i]=c

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

Submission status: Accepted

Solution code:
import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2:
        return False
    # 2は素数
    elif num == 2:
        return True
    # 偶数は素数ではない
    elif num % 2 == 0:
        return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = set()
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.add(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
# print(callIsPrime(10**5))

sosuu = callIsPrime(10**5)
count_dic = {}
count = 0
for i in range(1, 10**5, 2):
    if i in sosuu and (i+1)//2 in sosuu:
        count += 1
    count_dic[i] = count
# print(count_dic)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    # if r == l:
    #     print(count_dic[r]-count_dic[l]+1)
    # else:
    print(count_dic[r] - count_dic[max(l-2, 1)])

Submission status: Accepted

Solution code:
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True
prime = [0] * (10 ** 5 + 1)
prime[2] = 1
for i in range(3, 10 ** 5 + 1, 2):
    if is_prime(i):
        prime[i] = 1
s = [0] * (10 ** 5 + 2)
sum_ = 0
for i in range(1, 10 ** 5 + 1, 2):
    if prime[i] == 1 and prime[(i + 1) // 2] == 1:
        sum_ += 1
        s[i] = sum_
    else:
        s[i] = sum_
q = int(input())
lr = []
for i in range(q):
    lri = list(map(int, input().split()))
    lr.append(lri)
for i in range(q):
    print(s[lr[i][1]] - s[lr[i][0] - 2])

Submission status: Accepted

Solution code:
Q = int(input())

from functools import lru_cache
@lru_cache(maxsize=None)
def is_prime(n: int):
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    for p in range(3, int(n**0.5)+1, 2):
        if n % p == 0:
            return False
    return True

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

from bisect import bisect_left, bisect_right
for _ in range(Q):
    l, r = map(int, input().split())
    li = bisect_left(like_2017s, l)
    ri = bisect_right(like_2017s, r)
    print(ri-li)

Submission status: Accepted

Solution code:
from copy import deepcopy


def gen_2017_like(limit):
    p = [1 for _ in range(limit+1)]
    p[0] = p[1] = 0

    # prime?
    for i in range(2, len(p)):
        if not p[i]: continue
        else:
           for j in range(i*2, limit+1, i):
               p[j] = 0

    a = deepcopy(p)

    # like 2017?
    for i in range(len(a)):
        target = int((i+1)/2)
        if p[i] and p[target]:
            continue
        else:
            a[i] = 0
    return a



N = int(input())
R = []
L = []

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

limit = max(R)
sum_list = gen_2017_like(limit)
S = [0]*len(sum_list)
for i, e in enumerate(sum_list[1:]):
    S[i+1] = S[i] + e

for l, r in zip(L, R):
    ans = S[r] - S[l-1]
    print(ans)

Submission status: Accepted

Solution code:
import bisect
N = 10**6
dp = [1] * (N+1)
dp[0] =  dp[1] =  0
prime = []
for i in range(2,N+1):
    if dp[i]:
        for j in range(i*i, N+1, i):
            dp[j] = 0
like2017 = [0] * (N+1)
for n in range(N+1):
    if dp[n]==0:
        continue
    query = (n+1)//2
    if dp[query]==1:
        like2017[n] = 1


for n in range(N):
    like2017[n+1] += like2017[n]

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

Submission status: Accepted

Solution code:
import bisect
N = 10**6
dp = [1] * (N+1)
dp[0] =  dp[1] =  0
prime = []
for i in range(2,N+1):
    if dp[i]:
        for j in range(i*i, N+1, i):
            dp[j] = 0
for n in range(N+1):
    if dp[n]:
        prime.append(n)

like2017 = []
for p in prime:
    query = (p+1)//2
    idx = bisect.bisect_left(prime, query)
    if prime[idx] == query:
        like2017.append(p)
    

Q = int(input())
for q in range(Q):
    l, r = map(int,input().split())
    l = bisect.bisect_left(like2017, l)
    r = bisect.bisect_right(like2017, r)
    print (r-l)

Submission status: Accepted

Solution code:
import bisect
N = 10**6
dp = [0] * (N+1)
dp[0], dp[1] = 1, 1
prime = []
for i in range(2,N+1):
    if dp[i]==0:
        prime.append(i)
        for j in range(N//i+1):
            dp[j*i] = 1

like2017 = []
for p in prime:
    query = (p+1)//2
    idx = bisect.bisect_left(prime, query)
    if prime[idx] == query:
        like2017.append(p)
    

Q = int(input())
for q in range(Q):
    l, r = map(int,input().split())
    l = bisect.bisect_left(like2017, l)
    r = bisect.bisect_right(like2017, r)
    print (r-l)

Submission status: Accepted

Solution code:
from sys import stdin
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
prime_list=[i for i in range(2,100000) if is_prime(i)]
oppai=[0]*100000
oppai[1]=0
before=1
for num in prime_list:
    if (num+1)//2 in prime_list:
        oppai[before:num - 2] = [oppai[before]] * (num-1 - before)
        oppai[num-1]=oppai[before]+1
    else:oppai[before:num-1]=[oppai[before]]*(num-before)
    before=num-1
oppai[99991:99999]=[oppai[99990]]*8
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=list(map(int,stdin.readline().strip().split()))
    if a==b:
        bb = (oppai[b - 1])
        aa = (oppai[a - 2])
        count = bb - aa
        print(count)
    else:
        if a>=2:
            bb = oppai[b - 1]
            aa = oppai[a - 2]
            count = bb - aa
            print(count)
        else:
            bb = oppai[b - 1]
            count = bb
            print(count)

Submission status: Accepted

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


q=int(input())
LR=[list(map(int,input().split())) for _ in range(q)]
prime=prime(10**5)

DP=[0]*(10**5+1)
for i in prime:
    if i*2-1 in prime:
        DP[i*2-1]=1

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

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

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
INIT_VAL = 0
def DD2(d1,d2): return [[INIT_VAL]*d2 for _ in range(d1)]
def DD3(d1,d2,d3): return [DD2(d2,d3) for _ in range(d1)]
## math ##
MOD=10**9+7
def divc(x,y): return -(-x//y)
def divf(x,y): return x//y
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers"""
    is_prime = [True] * MAX_NUM
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(MAX_NUM):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_NUM, i):
                is_prime[j] = False
    return primes
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left

#======================================================#

def main():
    q = II()
    lr = [MII() for _ in range(q)]
    prims = set(get_primes(MAX_NUM=10**5))
    check_like_2017 = lambda x: x in prims and (x+1)//2 in prims
    like_2017 = [1 if check_like_2017(i) else 0 for i in range(10**5+1)]
    acc_like_2017 = list(acc(like_2017))
    for l,r in lr:
        print(acc_like_2017[r]-acc_like_2017[l-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def Eratosthene(n):
    prime = [1]*(n+1)
    prime[0] = 0
    prime[1] = 0

    for i in range(2, int(n**0.5)+1, 1):
        if prime[i]==0:
            continue
        for j in range(i+1, n+1, 1):
            if prime[j]==0:
                continue
            if j%i==0:
                prime[j] = 0
    return prime


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

for _ in range(Q):
    l,r = map(int, input().split())
    R.append(r)
    L.append(l)
Query = list(zip(L,R))
A = [0]*(10**5+1)
prime_list = Eratosthene(10**5)

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

S = [0]*(len(A)+1)

for i in range(len(A)):
    S[i+1] = S[i] + A[i]

for l,r in Query:
    print(S[r+1]-S[l])

Submission status: Accepted

Solution code:
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y
from itertools import accumulate as acc

class PrimeOptimizer:
    def __init__(self, MAX_NUM=10**3):
        """MAX_NUM以下の素数テーブルを生成する。
        生成した素数テーブルはprime_factorizationで使用する。
        """
        is_prime = [True] * MAX_NUM
        is_prime[0] = False
        is_prime[1] = False
        primes = []
        for i in range(MAX_NUM):
            if is_prime[i]:
                primes.append(i)
                for j in range(2*i, MAX_NUM, i):
                    is_prime[j] = False
        self.primes = primes

    def prime_factorization(self, x):
        """xを素因数分解する。
        分解先の素数はself.primesを利用する。
        @param x (int): 分解対象の正整数
        @return res (dict): key = 素数、value = 素数の数で構成される辞書
        """
        res = {}
        for prime in self.primes:
            while x % prime == 0:
                if not prime in res:
                    res[prime] = 0
                res[prime] += 1
                x //= prime
        if x > 1:
            res[x] = 1
        return res

def main():
    q = II()
    lr = [MII() for _ in range(q)]
    pm = PrimeOptimizer(MAX_NUM=10**5)
    prims = set(pm.primes)
    like_2017 = [0]*10**5
    for n in range(1,10**5):
        if n in prims and (n+1)//2 in prims:
            like_2017[n] = 1
    acc_like_2017 = list(acc(like_2017))
    for l,r in lr:
        print(acc_like_2017[r]-acc_like_2017[l-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

readline = sys.stdin.readline


def eratosthenes(n):
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    is_prime[4::2] = [False] * ((n-1) // 2 - 1)
    m = int(n**.5) + 1
    for i in range(3, m, 2):
        if is_prime[i]:
            is_prime[i*i::2*i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    # return [2] + [i for i in range(3, n, 2) if is_prime[i]]
    return is_prime


prime = eratosthenes(10**5+1)
num = (True if p and prime[(i+1)//2] else False for i, p in enumerate(prime))
cusum = [0] + list(accumulate(num))
Q = int(readline())
for _ in range(Q):
    l, r = map(int, readline().split())
    print(cusum[r+1] - cusum[l])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
"""
sosuu = [2]
A = 1+10**5
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    if all(L % L2 != 0 for L2 in sosuu):  # すべての既存素数で割り切れなかったら素数
        sosuu.append(L)
mat=[]
for i in range(len(sosuu)):
    if (sosuu[i]+1)//2 in sosuu:
        mat.append(sosuu[i])
print(mat)
"""
mat=[3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541, 613, 661, 673, 733, 757, 877, 997, 1093, 1153, 1201, 1213, 1237, 1321, 1381, 1453, 1621, 1657, 1753, 1873, 1933, 1993, 2017, 2137, 2341, 2473, 2557, 2593, 2797, 2857, 2917, 3061, 3217, 3253, 3313, 3517, 3733, 4021, 4057, 4177, 4261, 4273, 4357, 4441, 4561, 4621, 4933, 5077, 5101, 5113, 5233, 5413, 5437, 5581, 5701, 6037, 6073, 6121, 6133, 6217, 6337, 6361, 6373, 6637, 6661, 6781, 6997, 7057, 7213, 7393, 7417, 7477, 7537, 7753, 7933, 8053, 8101, 8221, 8317, 8353, 8461, 8521, 8677, 8713, 8893, 9013, 9133, 9181, 9241, 9277, 9601, 9661, 9721, 9817, 9901, 9973, 10333, 10357, 10453, 10837, 10861, 10957, 11113, 11161, 11317, 11497, 11677, 11701, 12073, 12157, 12241, 12301, 12421, 12433, 12457, 12541, 12553, 12601, 12721, 12757, 12841, 12853, 13093, 13381, 13417, 13681, 13921, 13933, 14437, 14593, 14737, 14821, 15013, 15073, 15121, 15241, 15277, 15361, 15373, 15733, 15901, 16033, 16333, 16381, 16417, 16573, 16633, 16657, 16921, 17041, 17053, 17077, 17257, 17293, 17377, 17881, 18013, 18097, 18133, 18181, 18217, 18253, 18301, 18313, 18397, 18481, 18553, 18637, 18793, 19237, 19441, 19477, 19717, 19801, 19813, 19861, 20353, 20533, 20641, 20857, 21001, 21061, 21193, 21277, 21313, 21577, 21661, 21673, 21817, 22093, 22501, 22573, 22621, 22993, 23053, 23173, 23557, 23677, 23773, 23917, 24097, 24421, 24481, 24781, 24841, 25033, 25153, 25237, 25561, 25657, 25933, 26017, 26293, 26317, 26437, 26497, 26821, 26833, 26881, 26953, 27073, 27253, 27337, 27361, 27457, 27997, 28057, 28297, 28393, 28813, 28837, 28921, 29101, 29473, 29641, 30181, 30241, 30517, 30553, 30577, 30637, 30661, 30697, 30781, 30853, 31081, 31237, 31321, 31333, 31357, 31477, 31573, 31873, 31981, 32173, 32377, 32497, 32533, 32833, 33037, 33301, 33457, 33493, 33757, 33961, 34057, 34213, 34273, 34381, 34513, 34897, 34981, 35317, 35521, 35677, 35977, 36097, 36241, 36433, 36457, 36793, 36877, 36901, 36913, 37273, 37321, 37357, 37573, 37717, 37957, 38281, 38461, 38833, 38953, 38977, 39217, 39373, 39397, 39733, 40093, 40177, 40213, 40693, 40813, 41017, 41221, 41281, 41413, 41617, 41893, 42061, 42337, 42373, 42793, 42961, 43117, 43177, 43201, 43321, 43573, 43597, 43633, 43717, 44053, 44101, 44221, 44257, 44293, 44893, 45061, 45337, 45433, 45481, 45553, 45613, 45841, 46021, 46141, 46261, 46861, 46993, 47017, 47161, 47353, 47521, 47533, 47653, 47713, 47737, 47797, 47857, 48121, 48193, 48337, 48673, 48757, 48781, 49033, 49261, 49393, 49417, 49597, 49681, 49957, 50221, 50341, 50377, 50821, 50893, 51157, 51217, 51241, 51481, 51517, 51637, 52057, 52081, 52237, 52321, 52453, 52501, 52813, 52861, 52957, 53077, 53113, 53281, 53401, 53917, 54121, 54133, 54181, 54217, 54421, 54517, 54541, 54673, 54721, 54973, 55057, 55381, 55501, 55633, 55837, 55921, 55933, 56053, 56101, 56113, 56197, 56401, 56437, 56701, 56773, 56821, 56857, 56893, 57073, 57097, 57193, 57241, 57373, 57457, 57853, 58153, 58417, 58441, 58537, 58573, 58693, 59053, 59197, 59221, 59281, 59341, 59833, 60217, 60337, 60373, 60637, 60733, 60937, 61057, 61153, 61261, 61297, 61561, 61657, 61681, 61717, 61861, 62137, 62473, 62497, 62533, 62653, 62773, 63313, 63397, 63541, 63697, 63781, 63913, 64153, 64237, 64381, 64513, 64717, 65173, 65293, 65413, 65437, 65497, 65557, 65677, 65881, 66301, 66361, 66601, 66697, 66853, 66973, 67057, 67153, 67273, 67477, 67537, 67741, 67777, 67933, 67993, 68113, 68281, 68521, 68737, 69001, 69073, 69457, 69493, 69697, 69877, 70117, 70177, 70297, 70501, 70621, 70921, 70981, 71233, 71341, 71353, 71593, 71821, 72073, 72481, 72613, 72901, 72937, 73141, 73417, 73477, 73561, 73693, 74077, 74317, 74377, 74713, 75013, 75133, 75181, 75721, 75793, 75913, 76333, 76561, 76597, 76753, 77137, 77641, 78157, 78193, 78277, 78877, 78901, 79333, 79357, 79537, 79657, 79693, 79801, 79873, 80077, 80173, 80221, 80473, 80701, 80713, 80917, 81013, 81181, 81517, 81637, 81853, 82021, 82153, 82261, 82561, 82981, 83077, 83221, 83233, 83437, 83617, 83701, 83773, 84121, 84313, 84673, 84697, 84793, 84913, 85297, 85333, 85453, 85717, 85933, 86353, 86413, 87181, 87253, 87337, 87421, 87433, 87517, 87553, 87973, 88117, 88177, 88237, 88261, 88513, 88741, 88897, 88993, 89293, 89833, 89917, 90121, 91081, 91381, 91393, 91513, 91957, 92041, 92557, 92761, 92821, 92893, 92941, 93097, 93133, 93493, 93637, 93913, 94033, 94117, 94273, 94321, 94441, 94573, 94777, 94837, 94993, 95257, 95317, 95401, 95581, 95617, 95713, 95737, 96097, 96157, 96181, 96493, 96517, 96973, 97081, 97177, 97501, 97561, 97777, 97813, 98017, 98737, 98953, 99277, 99577, 99661, 99877]

q=ii()
for i in range(q):
    x,y=mii()
    a=bisect_left(mat,x)
    b=bisect_right(mat,y)
    print(b-a)

Submission status: Accepted

Solution code:
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        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]]

q = int(input())

bit = [0]*(100001)
prime_list = set(prime(100001))
k = 0
for i in range(100000):
  bit[i+1] = bit[i]
  if i == 0:
    continue
  if i+1 in prime_list and (i+2)//2 in prime_list:
    bit[i+1] += 1

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

Submission status: Accepted

Solution code:
n = 10 ** 5 + 1
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False

a = [0] * n
s = [0] * (n + 1)

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):
    if i % 2 == 0:
        continue
    if is_prime[i] and is_prime[int((i + 1) / 2)]:
        a[i] = 1

for i in range(n):
    s[i + 1] = s[i] + a[i]

q = int(input())

l = [0] * q
r = [0] * q

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

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

Submission status: Accepted

Solution code:
q=int(input())
cnt=[0]*100001
def check(x):
    ret=1
    for k in range(2,int(x**(1/2))+1):
        if x%k==0:
            ret=0
            break
    return ret
for n in range(3,100000,2):
    if check(n)*check((n+1)//2)==1:
        cnt[n]=cnt[n-2]+1
    else:
        cnt[n]=cnt[n-2]
for m in range(4,100001,2):
    cnt[m]=cnt[m-1]
ans=[0]*q
for i in range(q):
    l,r=map(int,input().split())
    ans[i]=cnt[r]-cnt[l-1]
for i in range(q):
    print(ans[i])

Submission status: Accepted

Solution code:
import numpy as np
# import itertools
Q = int(input())
LR = [[int(x) for x in input().split()] for _ in range(Q)]
LR = np.array(LR)

# MAX = 10**5
# is_prime = [True] * MAX
# is_prime[0] = is_prime[1] = False
# for i in range(2, int(MAX**.5)+1):
#     if is_prime[i]:
#         for j in range(i*i, MAX, i):
#             is_prime[j] = False

# NUM = [0] * MAX
# for p in range(MAX):
#     if is_prime[p] and is_prime[(p+1)//2]:
#         NUM[p] += 1
# NUMcum = [0] + list(itertools.accumulate(NUM))
# for l, r in LR:
#     print(int(NUMcum[r+1] - NUMcum[l]))

## エラトステネスの篩
MAX = 10**5
is_prime = np.full(MAX, True)
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX**.5)+1):
    if is_prime[i]:
        is_prime[i*i::i] = False
        
NUM = np.zeros(MAX)
for p in range(MAX):
    if is_prime[p] and is_prime[(p+1)//2]:
        NUM[p] += 1

NUMcum = NUM.cumsum()

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

Submission status: Accepted

Solution code:
import itertools
Q = int(input())
LR = [[int(x) for x in input().split()] for _ in range(Q)]

MAX = 10**5
is_prime = [True] * MAX
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX**.5)+1):
    if is_prime[i]:
        for j in range(i*i, MAX, i):
            is_prime[j] = False

NUM = [0] * MAX
for p in range(MAX):
    if is_prime[p] and is_prime[(p+1)//2]:
        NUM[p] += 1
NUMcum = [0] + list(itertools.accumulate(NUM))
for l, r in LR:
    print(int(NUMcum[r+1] - NUMcum[l]))

Submission status: Accepted

Solution code:
import numpy as np
import itertools
Q = int(input())
LR = [[int(x) for x in input().split()] for _ in range(Q)]


## エラトステネスの篩
MAX = 10**5
is_prime = np.full(MAX, True)
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX**.5)+1):
    if is_prime[i]:
        is_prime[i*i::i] = False
        
NUM = np.zeros(MAX)
for p in range(MAX):
    if is_prime[p] and is_prime[(p+1)//2]:
        NUM[p] += 1

NUMcum = [0] + list(itertools.accumulate(NUM))

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

Submission status: Accepted

Solution code:
def abc084_d():

  def primes_list(n):
    # n以下の素数列挙
    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))
    return list(primes)

  # 素数リストを用意する
  primes = sorted(primes_list(10**5))

  # (n+1)//2 を素数判定するための準備
  is_prime = [False] * (10**5 + 10)
  for p in primes:
    is_prime[p] = True

  # 2017に似た数の累積個数 (1-index)
  acc_like = [0]
  for p in primes:
    this_like = 1 if is_prime[(p+1) // 2] else 0
    acc_like.append(acc_like[-1] + this_like)

  # 入力を受け取る
  q = int(input())
  query = [tuple(map(int, input().split())) for _ in range(q)]

  # クエリを処理する
  from bisect import bisect_left
  for l, r in query:
    # 2は素数だが奇数ではない、rは3以上でないと解が無い
    if r < 3:
      print(0)
      continue
    # 左側は3以下はカット
    l = max(l, 3)
    # 二分探索で範囲決める
    idx_l = bisect_left(primes, l)
    idx_r = bisect_left(primes, r+1)
    # 累積和から個数求める
    ans = acc_like[idx_r] - acc_like[idx_l]
    print(ans)

abc084_d()

Submission status: Accepted

Solution code:
import bisect
Q=int(input())
query=[list(map(int,input().split())) for _ in range(Q)]
n = 5*(10**4)
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)
like2019=[]
for k in primes:
    pf = {}
    m = 2*k-1
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1: pf[m] = 1
    #print(pf)
    keys = list(pf.keys())
    values = list(pf.values())
    if (len(values)==1)and(values[0]==1):
        like2019.append(2*k-1)
    #input()
#print(like2019)
for i in range(Q):
    l,r=map(int,query[i])
    lind=bisect.bisect_left(like2019,l-1)
    rind=bisect.bisect_left(like2019,r+1)
    print(rind-lind)

Submission status: Accepted

Solution code:
n=int(input())
q=[list(map(int,input().split())) for _ in range(n)]
MAX=100010
p=[1]*MAX
p[0]=0;p[1]=0
for i in range(2,MAX):
  if not p[i]:continue
  for j in range(i*2,MAX,i):p[j]=0
a=[0]*MAX
for i in range(MAX):
  if i%2==0:continue
  if p[i] and p[int((i+1)/2)]:a[i]=1
s=[0]*(MAX+1)
for i in range(MAX):
  s[i+1]=s[i]+a[i]
for i in range(n):
  print(s[q[i][1]+1]-s[q[i][0]])