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:
size = 10 ** 5 + 1
is_primes = [True] * size
is_primes[0] = False
is_primes[1] = False
for n in range(2, size):
    if not is_primes[n]:
        continue

    m = n * 2
    while m < size:
        is_primes[m] = False
        m += n

dp = [0] * size
for i in range(1, size):
    dp[i] = dp[i - 1]
    if i % 2 == 1 and is_primes[i] and is_primes[(i + 1) // 2]:
        dp[i] += 1

Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    print(dp[right] - dp[left - 1])

Submission status: Accepted

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


size = 10 ** 5 + 1
memo = [0] * size
for n in range(3, size):
    memo[n] = memo[n - 1]
    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2):
        memo[n] += 1

Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    print(memo[right] - memo[left - 1])

Submission status: Accepted

Solution code:
q=int(input())
from math import floor,sqrt
def isPrime(x):
  if x<2:
    return False
  elif x==2:
    return True
  elif x%2==0:
    return False
  for i in range(3,floor(sqrt(x))+1,2):
    if x%i==0:
      return False
  return True
def PrimeSet(x):
  p=set()
  for i in range(1,x+1):
    if isPrime(i):
      p.add(i)
  return p
prime1=PrimeSet(10**5)
prime2=set()
for j in range(1,10**5+1):
  if j%2:
    i=(j+1)//2
    if isPrime(i):
      prime2.add(j)
prime3=prime1&prime2
plist=[0]*(10**5+1)
for i in range(1,10**5+1):
  plist[i]=plist[i-1]
  if i in prime3:
    plist[i]+=1
for i in range(q):
  l,r=map(int,input().split())
  print(plist[r]-plist[l-1])

Submission status: Accepted

Solution code:
def pre_make_prime(N):
    is_prime = [True for _ in range(N + 1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, N + 1):
        if is_prime[i]:
            for j in range(i * 2, N + 1, i):
                is_prime[j] = False
    return is_prime


def resolve():
    N = 10**5
    is_prime = pre_make_prime(N)

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

    Q = int(input())
    for _ in range(Q):
        L, R = [int(i) for i in input().split()]
        print(arr_2017[R + 2] - arr_2017[L])


resolve()

Submission status: Accepted

Solution code:
def mips():
    return map(int,input().split())
def ii():
    return int(input())
def is_prime(n):
    if n == 1:
        return False
    i = 2
    while i*i <= n: #sqrt(n)までで十分。
        if n % i == 0:
            return False
        i += 1
    return True
Q = ii()
S = [0 for i in range(10 ** 5 + 1)]
N = 0
for i in [j for j in range(1,10 ** 5 + 1)]:
    if is_prime(i) and is_prime((i+1)//2):
        N += 1
        S[i] = N
    else:
        S[i] = N
for i in range(Q):
    l,r = mips()
    print(S[r]-S[l-1])

Submission status: Accepted

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

q = int(input())
n = 100000
ass = primes(n)
lkn = []
for p in ass:
    l = (p + 1) // 2
    if l in ass:
        lkn.append(p)
cnt = 0
pre = 1
ans = {}
lkn.append(100001)
for p in lkn:
    for i in range(pre,p,2):
        ans[i] = cnt
    cnt += 1
    pre = p
for i in range(q):
    l,r = map(int,input().split())
    l = max(l-2,1)
    print(ans[r] - ans[l])
    #print(ans[r],ans[l])
#print(lkn)

Submission status: Accepted

Solution code:
import numpy as np
def sieve(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
        else:
            if i==2:
                is_prime[2] = False
            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]]

N = 10**5+10
primes= sieve(N)
set_primes = set(primes)
tank = [3]
for x in primes:
    if (x+1)//2 in set_primes:
        tank.append(x)

arr = [0]*N
for t in tank:
    arr[t] = 1
arr = np.cumsum(arr).tolist()
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    print(arr[r] - arr[l-1])

Submission status: Accepted

Solution code:
n = 10**5
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

num_li = [0]*(n+1)
cnt = 0
for i in range(n+1):
    if is_prime[i] and (i+1)//2>0 and is_prime[(i+1)//2]:
        cnt+=1
    num_li[i]=cnt

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

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-
import sys
input=sys.stdin.readline
n = 10**5
#primes = set(range(3, n+1, 2))|set([2])
primes = set(range(3, n+1, 2)) #偶数は除く
for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*3, n+1, i*2))
primes.add(2)

Likes = [0] * (n+1)
cnt = 0
for i in range(1,n+1,2):
    Likes[i-1]=Likes[i-2]
    x = (i+1)//2
    if i in primes and (x in primes or x==2):
        Likes[i]=Likes[i-1] + 1
    else:
        Likes[i]=Likes[i-1]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
q = int(input())


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


prime_list = primes(100000)
familiar = [0]*100001
for p in prime_list:
    if (p+1)//2 in prime_list:
        familiar[p] = 1
s = [0]*100001
for i in range(100000):
    s[i+1] = s[i] + familiar[i+1]


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

Submission status: Accepted

Solution code:
Q = int(input())
MIN, MAX = 10**18, 0
LR = []
for q in range(Q):
    l, r = map(int, input().split())
    MIN = min(MIN, l)
    MAX = max(MAX, r)
    LR.append((l, r))

from math import sqrt
from itertools import accumulate
lis = [0]*(MAX+1)
search = [2] + [i for i in range(2, MAX+1) if i%2!=0]
lim = sqrt(MAX)
prime = set()
while 1:
    n = search[0]
    if n>=lim:
        break
    prime.add(n)
    if (n+1)//2 in prime:
        lis[n] = 1
    search = [i for i in search if i%n!=0]
for s in search:
    prime.add(s)
    if (s+1)//2 in prime:
        lis[s] = 1
clis = list(accumulate(lis))
for l, r in LR:
    print(clis[r]-clis[l-1])

Submission status: Accepted

Solution code:
import bisect

n = 10**5
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

num = [0] * (n + 1)

cnt = 0
for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if is_prime[(i + 1) // 2]:
            cnt += 1
    num[i] = cnt

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

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

Submission status: Accepted

Solution code:
def isPrime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    cur = 3
    while True:
        if cur * cur > x:
            break
        if x % cur == 0:
            return False
        cur += 2
    return True


Q = int(input())
num = [0] * 100010
for i in range(3,100001,2):
    if isPrime(i) and isPrime((i+1)//2):
        num[i] += 1
for i in range(0,100001):
    num[i+1] += num[i]


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

Submission status: Accepted

Solution code:
from itertools import accumulate
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
prime_set = set(get_sieve_of_eratosthenes(10**5+1))
like_2017_list =  [0 for _ in range(10**5+1)]
like_2017_set = set()
for n in range(1, 10**5, 2):
    if n in prime_set and (n+1)//2 in prime_set:
        like_2017_list[n] = 1
        like_2017_set.add(n)
like_2017_list = list(accumulate(like_2017_list))
# print(like_2017_list[:14])
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(like_2017_list[r]-like_2017_list[l-1])

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10000000)
Q = int(input())
l_r = [list(map(int, input().split())) for _ in range(Q)]

prime = []
def isprime(n):
    if n in prime:
        return True
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    
    return True


def like(x):
    if isprime(x) and isprime((x+1)//2):
        return True
    
    return False

x_dict = {1:0}
def count_like(x):
    if x in x_dict:
        return x_dict[x]
    x_dict[x] = count_like(x-1) + like(x)
    return x_dict[x]

for i in range(Q):
    print(count_like(l_r[i][1]) - count_like(l_r[i][0]) + int(like(l_r[i][0])))

Submission status: Accepted

Solution code:
N = int(input())
MAX=110000
S = [_+2 for _ in range(MAX)]
old = S
i = 0
while True:
  new = set([])
  t = old[i]
  for j in range(len(old)):
    if old[j] == t or old[j]%t != 0:
      new.add(old[j])
  if len(old) == len(new):
    break
  old = list(new)
  old.sort()
  i += 1


#print(old)
A = [0 for _ in range(MAX)]  
for i in range(MAX):
  if i%2 == 0:
    continue
  if i in new and (i+1)//2 in new:
    A[i] = 1
SUM = [0 for _ in range(MAX)] 
for i in range(1,MAX):
  SUM[i] += A[i]+SUM[i-1]
#print(SUM)

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

Submission status: Accepted

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

import sys
# import time
import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    class Eratos:
        def __init__(self, num):
            '''
            O(nlglgn) で num までの素数判定テーブルを作る
            >>> e = Eratos(10)
            >>> e.table
            [False, False, True, True, False, True, False, True, False, False, False]
            '''
            assert(num >= 1)
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
        
        def is_prime(self, num):
            '''
            O(1) で素数判定を行う
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            '''
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            '''
            O(√n) で素因数分解を行う
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            '''
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            # 素因数分解の結果を記録する辞書        
            factorized_dict = dict()
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                if num == 1:    # これ以上調査は無意味
                    break
                if num % p == 0:
                    cnt = 0
                    while num % p == 0:
                        num //= p
                        cnt += 1
                    factorized_dict[p] = cnt
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
        
        def enum_divisor(self, num):
            '''
            O(√n) で約数列挙を行う
            >>> e = Eratos(10000)
            >>> e.enum_divisor(4)
            [1, 2, 4]
            >>> e.enum_divisor(19)
            [1, 19]
            >>> e.enum_divisor(100)
            [1, 2, 4, 5, 10, 20, 25, 50, 100]
            '''
            divisor_small = []
            divisor_large = []
            for i in range(1, int(math.sqrt(num)) + 1):
                if num % i == 0:
                    divisor_small.append(i)
                    if i != num // i:
                        divisor_large.append(num // i)
            divisor_large.reverse()
            return divisor_small + divisor_large
    
    e = Eratos(10**5)
    similar_to_2017 = [0] * (10**5+1)
    for num in range(3, 10**5+1, 2):
        if e.is_prime(num) and e.is_prime((num+1)//2):
            similar_to_2017[num] = 1
    accum_similar_to_2017 = list(accumulate(similar_to_2017))
    
    q = ii()
    for _ in range(q):
        l, r = mi()
        print(accum_similar_to_2017[r] - accum_similar_to_2017[l-1])



if __name__ == "__main__":
    main()

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

like = []
for i in range(1,100000,2):
    if is_prime(i) and is_prime((i+1)//2):
        like.append(i)
like_set  = set(like)
q = int(input())
import bisect
for _ in range(q):
    l,r = map(int,input().split())
    a = bisect.bisect_left(like,l)
    b = bisect.bisect_right(like,r)
    print(b-a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

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

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primes = []
  while seachList[0] <= max:
    primes.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primes.extend(seachList)
  return primes

P = make_primes(100000)[1:]
like = []
for p in P:
  if len(factorization((p+1)//2)) == 1 and factorization((p+1)//2)[0][1] == 1:
    like.append(p)

imosu = [0 for i in range(101000)]
for i in like:
  imosu[i] += 1
  imosu[i+1] -= 1
  
ans = [0]
for i in imosu:
  ans.append(ans[-1]+i)
  
ruiseki = [0]
for i in ans:
  ruiseki.append(ruiseki[-1]+i)
Q = I()
for _ in range(Q):
  l,r = IL()
  print(ruiseki[r+2]-ruiseki[l+1])

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10


    def sieve_of_eratosthenes(upper_bound):
        upper_bound += 1
        P = [True] * upper_bound
        P[0] = P[1] = False
        for i in range(4,upper_bound,2):
            P[i] = False
        for i in range(3,int(upper_bound**0.5),2):
            if P[i]:
                for j in range(i**2,upper_bound,i):
                    P[j] = False
        return P

















    num_like2017 = [0]*(10**5+1)
    primes = sieve_of_eratosthenes(10**5)
    for i in range(1,10**5+1):
        if primes[i] and primes[(i+1)//2]:
            num_like2017[i] = num_like2017[i-1] + 1
        else:
            num_like2017[i] = num_like2017[i-1]
    out = deque()
    Q = II()
    for i in range(Q):
        l,r = LMIIS()
        out.append(num_like2017[r] - num_like2017[l-1])
    
    for o in out:
        print(o)

    
main()

Submission status: Accepted

Solution code:
def prime_all(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = is_prime[1] = False
    i = 2
    while i*i <= n:
        if is_prime[i]:
            j = 2*i
            while j <= n:
                is_prime[j] = False
                j += i
        i += 1       
    #prime_list = [i for i, x in enumerate(is_prime) if x == True]
    return is_prime
  
q = int(input())

max_N = 10**5

primes = prime_all(max_N)

prime_count = [0]*(max_N+1)

j=0
for i in range(2, max_N+1):
    if primes[i] and primes[(i+1)//2]:
        prime_count[i] = prime_count[i-1] + 1
    else:
        prime_count[i] = prime_count[i-1]
        
for i in range(q):
    l,r = map(int,input().split())
    print(prime_count[r] - prime_count[l-1])

Submission status: Accepted

Solution code:
import bisect

q = int(input())

def pr(n):
    is_prime = [True]*(n+2)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int((n+1)**0.5)+1):
        for j in range(2,i+1):
            if is_prime[i] == False:
                continue
            for k in range(2*i,n+1,i):
                is_prime[k] = False
                
    return is_prime
    
L = pr(10**5*2+2000)

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

for i in range(q):
    l,r = map(int,input().split())
    l_ = bisect.bisect_left(li,l)
    r_ = bisect.bisect_right(li,r)
    print(r_ - l_)

Submission status: Accepted

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

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


t,_ = sieve(100005)
m = [0]
cnt = 0
for i in range(100005):
    #分かりにくいけど奇数時のiは偶数です
    if i%2==0 and t[i] and t[(1+i)//2]:
        cnt+=1
    m.append(cnt)


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

Submission status: Accepted

Solution code:
from math import sqrt

q = int(input())

nums = [i for i in range(2, 10**5+1)]
primes = []
while nums[0] < sqrt(10**5):
    n = nums.pop(0)
    primes.append(n)
    new_nums = []
    for num in nums:
        if num % n != 0:
            new_nums.append(num)
    nums = new_nums
primes.extend(nums)
primes_set = set(primes)


flags = []
for i in range(10**5+1):
    flags.append(int(i in primes_set and (i+1)/2 in primes_set))
cum_flags = [0]*len(flags)
cum_flags[0] = flags[0]
for i in range(1, len(flags)):
    cum_flags[i] = cum_flags[i-1]+flags[i]

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

p_list = primes(10 ** 5)
cnt = [0] * (10 ** 5 + 2)
for i in range(1, (10 ** 5 + 1), 2):
    if p_list[i] and p_list[(i + 1) // 2]:
        cnt[i] += 1
cnt_sum = list(accumulate(cnt))

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

Submission status: Accepted

Solution code:
from math import sqrt
M = 10**6
p = [1 for i in range(M+1)]
p[0] = 0
p[1] = 0
for x in range(2, int(sqrt(M))+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0

a = [0 for i in range(M+1)]
for i in range(M):
    if i%2 != 0 and p[i] and p[(i+1)//2]:
        a[i] = 1

ans = [0 for i in range(M)]
for i in range(1, M):
    ans[i] = ans[i-1] + a[i]

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

Submission status: Accepted

Solution code:
import itertools

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

a = sieve(10**5)
b = [0] * (10**5 + 1)
for i in range(10**5+1):
  if a[i] and a[(i+1)//2]:
    b[i] = 1

b = list(itertools.accumulate(b))
ans = []
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  ans.append(b[r] - b[l-1])

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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