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:
table_prime_numbers = [True for _ in range(10 ** 5)]
table_2017_numbers = [False for _ in range(10 ** 5)]
table_2017_numbers_acm = [0 for _ in range(10 ** 5)]

def init_tables():
  table_prime_numbers[0] = table_prime_numbers[1] = False
  for i in range(2, 10 ** 5):
    if table_prime_numbers[i]:
      for j in range(i * 2, 10 ** 5, i):
        table_prime_numbers[j] = False
        
  for i in range(2, 10 ** 5):
    if table_prime_numbers[i]:
      if (i * 2 - 1 < 10 ** 5) and table_prime_numbers[i * 2 - 1]:
        table_2017_numbers[i * 2 - 1] = True
  
  for i in range(2, 10 ** 5):
    table_2017_numbers_acm[i] = table_2017_numbers_acm[i - 1] + int(table_2017_numbers[i])
      
  return

def cumul(n):
  return table_2017_numbers_acm[n]

def result(l, r):
  return cumul(r) - cumul(l - 1)

def main():
  q = int(input())
  
  for _ in range(q):
    l, r = map(int, input().split())
    print(result(l, r))

  return

if __name__ == "__main__":
  init_tables()
  main()

Submission status: Accepted

Solution code:
import math

def main():

    Q = int(input())
    query = []
    max_r = 0
    for _ in range(Q):
        l, r = map(int, input().split())
        query.append([l, r])
        max_r = max(max_r, r)

    primes = set()
    for i in range(2, max_r+1):
        if isprime(i):
            primes.add(i)

    # print(primes)
    count = [0]
    for i in range(1, max_r+1):
        if i % 2 == 1 and i in primes and (i+1) // 2 in primes:
            count.append(count[-1] + 1)
        else:
            count.append(count[-1])

    # print(count)
    for l, r in query:
        print(count[r] - count[l-1])


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

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

def main():
    Q = int(input())
    N = 10 ** 5
    num_list = [0] * (N + 5)

    for i in range(1,N+1):
        if is_prime(i) and is_prime((i+1)//2):
            num_list[i] = 1

    sum_num = [0] * (N + 6)

    for i in range(1,N+2):
        sum_num[i+1] = sum_num[i] + num_list[i]

    sum_num.pop(0)

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



main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
sys.setrecursionlimit(200000)
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

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

from copy import deepcopy
class CumulativeSum():
    def __init__(self, arr: list):
        self.data = deepcopy(arr)
        for i in range(1, len(self.data)):
            self.data[i] += self.data[i - 1]

    def _query(self, k: int) -> int:
        """[0,k]の和"""
        if k < 0:
            return 0
        else:
            return self.data[min(k, len(self.data) - 1)]

    def query(self, l: int, r: int) -> int:
        """[l,r)の和"""
        if l > r:
            return 0
        else:
            return self._query(r - 1) - self._query(l - 1)

    def __str__(self):
        return str(self.data)
    def __getitem__(self, k):
        return self.data[k]

def isOK(n):
    return n > 2 and isPrime(n) and isPrime((n + 1) / 2)

def main():
    Q = ii()
    v = [0] * 100001
    for i in range(100000 + 1):
        if isOK(i):
            v[i] = 1
    c = CumulativeSum(v)
    for i in range(Q):
        l, r = mi()
        print(c.query(l, r + 1))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import bisect
  
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

def get_like_2017(N):
  nums = set([i for i in range(2,N+1)])
  for i in range(2, int(math.sqrt(N))+1):
    for j in range(2,int(N//i)+1):
      if i*j in nums: nums.remove(i*j)
  
  nums_like_2017 = set([])
  for num in nums:
    if is_prime(int((num+1)/2)) is True:  nums_like_2017.add(num)
  return nums_like_2017

nums_like_2017 = sorted(list(get_like_2017(10**5)))

Q = int(input())
for _ in range(Q):
  l,r = map(int, input().split())
  idx_l = bisect.bisect_left(nums_like_2017, l)
  idx_r = bisect.bisect_right(nums_like_2017, r)
 
  print(idx_r-idx_l)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def conb(n,r): return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
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 = inp()
L = [0] * q
R = [0] * q
for i in range(q):
    L[i],R[i] = inpl()
    L[i] = (L[i]+1)//2
    R[i] = (R[i]+1)//2
# print(L,R)
cnt = [0] * ((10**5+10)//2)
for i in range(1,(10**5+5)//2):
    if is_prime(i) and is_prime(i+i-1):
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]
for i in range(q):
    print(cnt[R[i]] - cnt[L[i]-1])

Submission status: Accepted

Solution code:
from bisect import bisect_left

Q = int(input())

prime = [2, 3]
for i in range(5, 10 ** 5 + 1, 2) :
    flg = True
    for p in prime :
        if p * p > i :
            break
        if i % p == 0 :
            flg = False
            break
    if flg :
        prime.append(i)
        
like2017 = []
for p in prime :
    if (p + 1) // 2 in prime :
        like2017.append(p)
        
for _ in range(Q) :
    l, r = map(int, input().split())
    print(bisect_left(like2017, r + 1) - bisect_left(like2017, l))

Submission status: Accepted

Solution code:
#エラトステネスの篩
MAX = 101010
#iが素数だったら1(True)を、合成数であったら0(False)を返す配列を作ればよい
is_prime = [1]*MAX #最初は1(True)を入れておく
is_prime[0] = 0
is_prime[1] = 0 #[0]と[1]は当然非素数
for i in range(2,MAX):
    if is_prime[i] == 0:#もしもiが素数じゃなかったら
        continue #次の操作は行わず次のiの判定へ
    for j in range(i*2, MAX, i): #iが素数なら2i,3i,...は⇒
        is_prime[j] = 0 #合成数

#入力の受け取り
Q = int(input())
l = []
r = []
for i in range(Q):
    L,R=map(int,input().split())
    l.append(L)
    r.append(R)

#2017-like かどうか
MAX = 101010
a=[0]*MAX
for i in range(MAX+1):
    if i%2 == 0:
        continue
    elif is_prime[i] and is_prime[(i+1)//2]:#2017-likeならば⇒
        a[i] = 1 #配列a[i]を１（True）に書き換える

#累積和
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:
# 2019/09/06

input=open(0).readline
q=int(input())

lr=[]
mxr=0

for i in range(q):
    l,r=map(int,input().split())
    lr.append((l,r))
    mxr=max(mxr,r)

def sieve(n):
    end=int(pow(n,0.5))+1
    is_prime=[True]*(n+1)
    is_prime[0]=False
    is_prime[1]=False

    for i in range(2,end+1):
        if not is_prime[i]:continue
        for j in range(i*2,n+1,i):
            is_prime[j]=False
    return is_prime

prime=sieve(mxr)

x=[0]
cnt=0
for i in range(1,mxr+1):
    if prime[i]&prime[(i+1)//2]:
        cnt+=1
    x.append(cnt)
for l,r in lr:
    print(x[r]-x[l-1])

Submission status: Accepted

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

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

    MAX = int(1e5)
    MAX_PRIME = MAX
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    count = [0] * (MAX+1)
    for p in primes:
        if p&1:
            tmp = (p + 1) // 2
            if is_prime[tmp]:
                count[p] = 1
    for i in range(1, MAX+1):
        count[i] += count[i-1]
    
    # print(count[:10])
    for i in range(Q):
        l, r = lr[i]
        print(count[r] - count[l-1])
    



if __name__ == "__main__":
    main()

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



Q = int(input())

slis = primes(10 ** 5)
sdic = {}

for i in slis:
    sdic[i] = 1

#print (len(sdic))

"""
for i in range(10 ** 5 - 2):

    i += 3

    flag = True

    for j in sdic:
        if i % j == 0:
            flag = False

    if flag:
        sdic[i] = 1


#print (sdic)
"""

adic = {}
adic[-1] = 0
for j in range(10 ** 5 // 2):

    now = 1 + j * 2

    if now in sdic and (now + 1) // 2 in sdic:
        adic[now] = adic[now-2] + 1

    else:
        adic[now] = adic[now-2]

for i in range(Q):

    l,r = map(int,input().split())

    print (adic[r] - adic[l-2])

Submission status: Accepted

Solution code:
from bisect import*
p=[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]
for _ in [0]*int(input()):
 l, r = map(int, input().split())
 print(bisect_right(p, r)-bisect_left(p, l))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def is_prime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
            exit()
    return True

L=[0]*(10**5+1)
cnt=0
for i in range(3,10**5+1):
    if is_prime(i) and is_prime((i+1)//2):
        cnt+=1
    L[i]=cnt

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

Submission status: Accepted

Solution code:
Q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(Q)]
primes = [2]
MAX = 10**5
p_list = [0] * (MAX+1)
cnt = 0
for i in range(3, MAX+1):
  is_prime = True
  likely = False
  for prime in primes:
    if i%prime == 0:
      is_prime = False
      break
    if (i+1)//2 == prime:
      likely = True
      break
    elif (i+1)//2 < prime:
      break
    else:
      continue
  if is_prime:
    primes.append(i)
    if likely:
      cnt += 1
  p_list[i] = cnt

for l, r in queries:
  if p_list[l] > p_list[l-1]:
    print(p_list[r]-p_list[l]+1)
  else:
    print(p_list[r]-p_list[l])

Submission status: Accepted

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

q=int(input())
lr=[tuple(map(int, input().split())) for _ in range(q)]
is_primes=makeIsPrimeList(10**5)
mylst=[0]*(10**5+1)
cnt=0
for i in range(len(mylst)):
  if is_primes[i] and is_primes[(i+1)//2]:
    cnt+=1
  mylst[i]=cnt
for l, r in lr:
  print(mylst[r]-mylst[l-1])

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    pl = {}
    p = [True] * (10 ** 5 + 1)
    p[0] = False
    p[1] = False
    cnt = 0
    pll = [0] * (10 ** 5 + 1)
    for i in range(2, len(p)):
        if p[i]:
            pl[i] = 1
            for j in range(i, len(p), i):
                p[j] = False
        if i % 2 != 0:
            if (i + 1) // 2 in pl and i in pl:
                cnt += 1
        pll[i] = cnt
    q = int(input().rstrip('\n'))
    lr = [list(map(int, input().rstrip('\n').split())) for _ in range(q)]
    for l, r in lr:
        print(pll[r] - pll[l-1])


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
Q = int(input())

LR = []
for _ in range(Q):
    l,r = map(int, input().split())
    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: True for i in range(n + 1) if is_prime[i]}

prime_dict = primes(10**5)
like_2017 = []
for n in prime_dict:
    if (n+1)//2 in prime_dict:
        like_2017.append(n)
#print(like_2017)
like_2017 = list(sorted(like_2017))


from bisect import bisect_left, bisect_right

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    return i

for l, r in LR:
    if l == r:
        if l in like_2017:
            print(1)
        else:
            print(0)
    else:
        l_idx = index(like_2017, l)
        r_idx = index(like_2017, r)
        if r in like_2017:
            r_idx += 1
        print(r_idx-l_idx)

Submission status: Accepted

Solution code:
import math
Q = int(input())

def sosuu(x):
  if x == 1:
    return False
  else:
    for i in range(1,int(math.sqrt(x))):
      if x % (i+1) == 0:
        return False
    return True

table=[0]*50001
for i in range(1,50001):
  if sosuu(2*i - 1) and sosuu(i):
    table[i]=table[i-1] + 1
  else:
    table[i]=table[i-1]
    
ans=[0]*Q
for i in range(Q):
  l,r=map(int,input().split())
  ans[i]=table[(r+1)//2] - table[(l+1)//2 - 1]
  
for i in range(Q):
  print(ans[i])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    m = II()
    print(48-m)
    return

#B
def B():
    a, _ = LI()
    s = S()
    ans = list(map(str, range(10)))
    for num, si in enumerate(s):
        if num != a:
            if si in ans:
                continue
            print("No")
            return
        else:
            if si == "-":
                continue
            print("No")
            return
    print("Yes")
    return

#C
def C():
    n = II()
    csf = LIR(n - 1)
    for i in range(n - 1):
        b = 0
        for k in range(i, n - 1):
            c, s, f = csf[k]
            if b <= s:
                b = s + c
            else:
                b += c + (-b % f)
        print(b)
    print(0)
    return

#D
def D_():
    a = II()
    ans = inf
    b = 0
    for _ in range(1, 10 ** 5):
        b += a
        ans = min(ans, sum(list(map(int, list(str(b))))))
    print(ans)
    return

def D():
    q = II()
    def primes(n):
        """ Input n>=6, Returns a list of primes, 2 <= p < n """
        """ 6以上の数であれば p (素数) <= n のlistを返す """
        n, correction = n-n%6+6, 2-(n%6>1)
        sieve = [True] * (n//3)
        for i in range(1,int(n**0.5)//3+1):
            if sieve[i]:
                k=3*i+1|1
                sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
                sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
        return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]
    primelis = primes(10 ** 5)
    d = defaultdict(int)
    for i in primelis:
        d[i] += 1
    dp = [0]
    for i in range(3, 10 ** 5, 2):
        dp.append(dp[-1] + (1 if (d[i] and d[(i + 1) // 2]) else 0))
    for i in range(q):
        l, r = map(lambda x: x // 2, LI())
        if l == 0:
            print(dp[r])
            continue
        print(dp[r] - dp[l - 1])



#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
## N以下の数の素数を全て列挙する
def prime_table(n):
  list = [True for _ in range(n+1)]
  list[0] = False ## 0は素数ではない
  list[1] = False ## 1は素数ではない
  i = 2
  ## 残っている最小の素数を選び、その倍数をFalseにする
  while i**2 <= n:
    if list[i]:
      j = i + i
      while j <= n:
        list[j] = False
        j += i
    i += 1
  table = [i for i in range(n+1) if list[i]]
  return table

## リストの中から"2017に似た数"を全て列挙する
## 2以外の素数は全てN=6M+1, 6M-1の形に書ける
## 前者が"似た数"の場合は「Mが偶数」が必要 ...(*)
## 後者が"似た数"の場合はN=5のみ
## まとめると、"似た数"は、3と5と(*)を満たす数
def ABC084D(prime_table):
  lst = [3, 5]
  for i in range(len(prime_table)):
    if (prime_table[i] - 1) % 12 == 0:
      if (prime_table[i] + 1) // 2 in prime_table:
        lst.append(prime_table[i])
  return lst


import bisect

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


primes = prime_table(100000) ## 100000以下の素数を全て列挙
lst = ABC084D(primes) ## その中から"2017に似た数"を全て列挙
for i in range(Q):
  ans = bisect.bisect_right(lst,LR[i][1]) - bisect.bisect_left(lst,LR[i][0])
  print(ans)

Submission status: Accepted

Solution code:
# ABC084D - 2017-like Number
import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right


def get_primes(n: int) -> list:
    # return a list of primes <= n
    n += 1  # include n itself
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(Q))
    P = get_primes(10 ** 5)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]
    bsr, bsl = bisect_right, bisect_left
    ans = [bsr(selected_P, r) - bsl(selected_P, l) for l, r in A]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC084D - 2017-like Number
import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right


def get_primes(n: int) -> list:
    # return a list of primes <= n
    n += 1  # include n itself
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(Q))
    P = get_primes(10 ** 5)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]
    ans = []
    bsr, bsl = bisect_right, bisect_left
    for l, r in A:
        x = bsr(selected_P, r) - bsl(selected_P, l)
        ans += [x]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC084D - 2017-like Number
import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right


def get_primes(n):
    # return a list of primes <= n
    n += 1  # include n itself
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(Q))
    _, R = zip(*A)
    lim = max(R)
    P = get_primes(lim)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]
    ans = []
    for l, r in A:
        x = bisect_right(selected_P, r) - bisect_left(selected_P, l)
        ans += [x]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC084D - 2017-like Number
import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right


def get_primes(n):
    # return a list of primes <= n
    n += 1  # include n itself
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(Q))
    P = get_primes(10 ** 5)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]
    ans = []
    for l, r in A:
        x = bisect_right(selected_P, r) - bisect_left(selected_P, l)
        ans += [x]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

A = [0 for i in range(50000)]
for i in range(1, 50000):
  A[i] = A[i-1]
  if isp(i+1) and isp(2*i+1):
    A[i] += 1
    
Q = int(input())
for i in range(Q):
  r, l = map(int, input().split())
  print(A[l//2]-A[max(0, r//2-1)])

Submission status: Accepted

Solution code:
import math


def sosu(N):
    tbl = [0] * (N + 1)
    tbl[0] = 1
    tbl[1] = 1
    lim = math.ceil(math.sqrt(N))
    for i in range(2, lim + 1):
        if tbl[i] == 0:
            for j in range(2, N + 1):
                tmp = i * j
                if tmp > N: break
                tbl[tmp] = 1
    return tbl


ptbl = sosu(10 ** 5)

memo = [0] * (10 ** 5 + 1)
for i in range(2, len(memo)):
    memo[i] = memo[i - 1]
    if ptbl[i] == 1: continue
    if ptbl[(i + 1) // 2] == 0:
        memo[i] += 1

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

Submission status: Accepted

Solution code:
Ps = set()
M = [False]*100001
p = 2
while p <= 100000:
  if not(M[p]):
    Ps.add(p)
    for i in range(p, 100000, p):
      M[i] = True
  p += 1
#print(sorted(Ps))
r = 0
Ss = [0]*100001
for i in range(100000):
  if i%2 == 1 and i in Ps and (i+1)//2 in Ps:
    r += 1
  Ss[i] = r
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  re = Ss[r]-Ss[l-1]
  print(re)

Submission status: Accepted

Solution code:
import bisect
a = [True] * 100001
a[0] = False
a[1] = False
p = []
for i in range(2, 100001):
    if a[i]:
        for j in range(i * 2, 100001, i):
            a[j] = False
        if i % 2 != 0 and a[(i + 1) // 2]:
            p.append(i)
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(p, r) - bisect.bisect_left(p, l))

Submission status: Accepted

Solution code:
import numpy as np
import bisect

def prime_number(num):  
  if num == 0 or num == 1:
    return False
  
  if num > 2 and num % 2 == 0:
    return False  
  
  for i in range(3, int(np.sqrt(num)+1)):
    if num % i == 0:
      return False
  
  return True

def check(num):
  if prime_number(num) and prime_number((num+1)//2):
    return True
    
  return False
    
checked = [i for i in range(10**5+1) if check(i)]

# r_list = [sum(checked[:(i+1)]) for i in range(10**5+1)]

# print(checked)

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

Submission status: Accepted

Solution code:
import bisect
a = [True] * 100001
a[0] = False
a[1] = False
p = []
for i in range(2, 100001):
    if a[i]:
        for j in range(i * 2, 100001, i):
            if a[j]:
                a[j] = False
        if i % 2 != 0 and a[(i + 1) // 2]:
            p.append(i)
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(p, r) - bisect.bisect_left(p, l))

Submission status: Accepted

Solution code:
import math
import bisect
q=int(input())
query=[list(map(int,input().split())) for i in range(q)]
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
prime = set(primes(10**5))
ok_n = []
for i in range(1,10**5+1):
  if i in prime and (i+1)//2 in prime:
    ok_n.append(i)
for i in range(q):
  x1=bisect.bisect_left(ok_n,query[i][0])
  x2=bisect.bisect_right(ok_n,query[i][1])
  print(x2-x1)

Submission status: Accepted

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

n=10**5
sievebd=n//2
sieve=[True]*sievebd
limit=int(n**.5)//2
sieve[0]=0
for i in range(limit):
    if sieve[i]:
        for j in range(2*i*(i+1),sievebd,2*i+1):
            sieve[j]=False
for i in range((sievebd-1)//2,0,-1):
    if not sieve[i]:sieve[2*i]=False
for i in range(3,sievebd,2):sieve[i]=False
for i in range(1,sievebd):sieve[i]+=sieve[i-1]
q=int(input())
l=[list(map(int,input().split())) for _ in [0]*q]
for i in range(q):
    print(sieve[(l[i][1]-1)//2]-sieve[max(0,(l[i][0]-1)//2-1)])