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:
def pm_table(n):
    """
    素数テーブル
    n以下の素数のリストを返却する
    :param n:
    """
    res = [1] * (n + 1)
    res[0] = 0
    res[1] = 0

    for i in range(2, n):
        if i ** 2 > n:
            break

        if res[i] == 1:
            for j in range(i * 2, n + 1, i):
                res[j] = 0
    return res


N = 10 ** 5
pm = pm_table(N)

def is_prime(x):
    return pm[x]


s = [0] * (N + 2)
a = [0] * (N + 1)

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

q = int(input())
LR = np.array([input().split() for _ in range(q)], np.int64)
L, R = zip(*LR)

is_prime = np.zeros(max(R) + 1, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
M = int(max(R) ** .5) + 1
for p in range(3, M, 2):
    if is_prime[p]:
        is_prime[p * p::p + p] = 0

A = np.zeros(max(R) + 1, np.bool)
for i in range(max(R) + 1):
    j = (i + 1) // 2
    if is_prime[i] and is_prime[j]:
        A[i] = 1
S = np.zeros(len(A) + 1, np.int32)
S[1:] = np.cumsum(A)
for i in range(q):
    print(S[R[i] + 1] - S[L[i]])

Submission status: Accepted

Solution code:
import math

def main():
    Q = int(input())
    #エラトステネスのふるい
    is_prime = [True]*(10**5+1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, int(math.sqrt(10**5))+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, 10**5+1, i):
            is_prime[j] = False
            
    a = [0]*(10**5+1) #2017-likeな数字かどうかを判定する配列
    for i in range(1, 10**5+1):
        if is_prime[i] and is_prime[(i+1)//2]:
            a[i] = 1
            
    s = [0] * (10**5+1) #累積和
    for i in range(10**5):
        s[i+1] = s[i] + a[i]
    
    for _ in range(Q):
        l, r = map(int, input().split())
        print(s[r+1]-s[l])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
inf = float("inf")

Q = int(input())
queries = []

for _ in range(Q):
    l, r = map(int, input().split())
    queries.append([l, r])
# print(queries)

MAX = 10 ** 5 + 1

# Sieve of Eratosthenes
is_prime = [1 for _ in range(MAX)]
is_prime[0] = 0
is_prime[1] = 0

for i in range(2, MAX):
    if not is_prime[i]:
        continue
    j = i + i
    while j < MAX:
        is_prime[j] = 0
        j += i

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

com_sum = [0 for _ in range(MAX + 1)]
for i in range(MAX):
    com_sum[i + 1] = com_sum[i] + a[i]

for left, right in queries:
    # print(f"s[left] = {com_sum[left]}")
    # print(f"s[right] = {com_sum[right]}")
    x = com_sum[right + 1] - com_sum[left]
    print(x)

Submission status: Accepted

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

def eratosthenes(n):
  a=[i for i in range(2,n+1)]
  prime=[]
  while True:
    p=min(a)
    if p**2>n:
      break
    prime.append(p)
    i=0
    while i<len(a):
      if a[i]%p==0:
        a.pop(i)
        continue
      i+=1
  for i in a:
    prime.append(i)
  return prime

ans=[0]*(10**5+1)
flag=[0]*(10**5+1)
for i in eratosthenes(10**5):
  flag[i]=1
cnt=0
for i in range(1,10**5+1):
  if flag[i]==1 and flag[(i+1)//2]==1:
    cnt+=1
  ans[i]=cnt
for i in range(q):
  print(ans[r[i]]-ans[l[i]-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ma = lambda : map(int,input().split())
ni = lambda : int(input())

n = 10**5+1
primes = [1]*n
primes[0] =0
primes[1] =0
for i in range(2,int(n**0.5)+1):
    if primes[i] ==1:
        for j in range(2*i,n,i):
            primes[j] = 0
p2017 = [0]*n
for i in range(1,n):
    p2017[i] = p2017[i-1]
    if primes[i] and primes[(i+1)//2]:
        p2017[i]+=1
q = ni()
for i in range(q):
    l,r = ma()
    print(p2017[r]-p2017[l-1])

Submission status: Accepted

Solution code:
import math
Q = int(input())#numの数の個数
Query = []
maxn=0
for _ in range(Q):
    l,r = map(int,input().split())
    Query.append((l,r))
    maxn = max(maxn,r)
N = maxn
num = [0]*(N+2)#部分和を計算したい数列
def souwa(left,right,ruisekiwa):#0based,numの[left,right)間の総和を計算
   return ruisekiwa[right]-ruisekiwa[left]
def using_sqrt(N):#入力 対象の整数,出力,素数ならば1,合成数ならば1
    flag = 0
    for i in range(2,math.floor(math.sqrt(N))+1):
        if N % i == 0:
            flag = 1
            break
        else:
            continue
    if flag == 1:
        return 0
    else:
        return 1

for i in range(1,N+2,2):
    if using_sqrt(i)==1 and using_sqrt((i+1)//2)==1:
        num[i] = 1
ruisekiwa = [0]*(N+2)
ruisekiwa[0] = 0
num[1] =0
for i in range(1,N+2):#累積和の前処理
    ruisekiwa[i]=num[i-1]+ruisekiwa[i-1]

for q in Query:
    print(souwa(q[0],q[1]+1,ruisekiwa))

Submission status: Accepted

Solution code:
from itertools import count

N = 10 ** 5 + 10

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

# ほぼO(N)
for i in range(N):
  if is_prime[i]:
    for j in count(2 * i, i):
      if j >= N:
        break
      is_prime[j] = False
      
is_2017_like_number = [0] * N

# O(N)
for i in range(N):
  if i % 2 != 0 and is_prime[i] and is_prime[(i + 1) // 2]:
    is_2017_like_number[i] = 1
    
cusum = [0] * (N + 1)

for i in range(N):
  cusum[i + 1] = cusum[i] + is_2017_like_number[i]
  
Q = int(input())

for _ in range(Q):
  l, r = map(int, input().split())
  r += 1  # 操作しやすいように [l, r) にする
  
  print(cusum[r] - cusum[l])

Submission status: Accepted

Solution code:
Q=int(input())

def prime_sieve(n):
  prime_list=[True]*n
  prime_list[0]=False
  prime_list[1]=False
  for i in range(2,int(n**0.5)+1):
    if not prime_list[i]:
      continue
    else:
      for j in range(i**2,n,i):
        prime_list[j]=False
  
  return prime_list
  #return [i for i in range(n) if is_prime_list[i]]

prime_list=prime_sieve(10**5+1)
#print(prime_list[:10])
  
plist=[0]*(10**5+1)
for i in range(3,10**5+1,2):
  if prime_list[i] and prime_list[(i+1)//2]:
    plist[i]=1
#print(plist[:10])

slist=[0]*(10**5+1)
for i in range(3,10**5+1):
  slist[i]=plist[i]+slist[i-1]
#print(slist[:10])
  
for i in range(Q):
  l,r=map(int,input().split())
  print(slist[r]-slist[l-1])

Submission status: Accepted

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

num = [0]*100010

def is_prime(n):
    # nが素数かどうか判定
    if n == 1:
        return False

    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    
    return True

for i in range(1,100010):
    if i%2 == 1 and is_prime(i) and is_prime((i+1)/2):
        num[i] = num[i-1]+1
    else:
        num[i] = num[i-1]

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

Submission status: Accepted

Solution code:
Q=int(input())

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

plist=[False]*(10**5+3)
for i in range(3,10**5+3,2):
  if isPrime(i) and isPrime((i+1)//2):
    plist[i]=True
#print(plist[:10])

slist=[0]*(10**5+3)
for i in range(3,10**5+3):
  if plist[i]:
    slist[i]=slist[i-1]+1
  else:
    slist[i]=slist[i-1]
#print(slist[:10])
  
for i in range(Q):
  l,r=map(int,input().split())
  print(slist[r]-slist[l-1])

Submission status: Accepted

Solution code:
import math
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:return False
    return True
flg = [1 if (i%2==1 and is_prime(i) and is_prime((i+1)//2)) else 0 for i in range(100001)] 
for i in range(1,100001):flg[i]+=flg[i-1]
for i in range(int(input())):
    l,r= map(int,input().split())
    print(flg[r]-flg[l-1])

Submission status: Accepted

Solution code:

def resolve():
    # エラトステネスのふるい
    def make_primes_table(n):
        if n < 2:
            return [False]*n
        is_prime = [True]*n
        is_prime[0] = False
        is_prime[1] = False
        for i in range(2, int(n**0.5)):
            if is_prime[i]:
                for j in range(i**2, n, i):
                    is_prime[j] = False
        return is_prime

    MAX_N = 10**5+1
    primes_table = make_primes_table(MAX_N)
    cnt = [0]*MAX_N
    for i in range(2, MAX_N):
        if primes_table[i] and primes_table[(i+1)//2]:
            cnt[i] += 1

    for i in range(1, MAX_N):
        cnt[i] += cnt[i-1]

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import math

if __name__ == '__main__':
    p = [0 for k in range(100000)]
    p[1] = 1
    for k in range(3, 100000, 2):
        f = 1
        for l in range(2, int(math.sqrt(k)) + 1):
            if k % l == 0:
                f = 0
                break
        if f == 1:
            p[k] = 1

    check = [0 for k in range(100000)]
    check[3] = 1
    for k in range(3, 100000, 2):
        if p[k] + p[(k + 1) // 2] == 2:
            check[k] = 1
    for k in range(1, 100000):
        check[k] += check[k - 1]
    for k in range(int(input())):
        l, r = map(int, input().split())
        print(check[r] - check[l - 1])

Submission status: Accepted

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

Q = int(input())

dp = {1: 0}

for i in range(10**5)[3::2]:
  if is_prime(i) and is_prime((i+1)//2):
    dp[i] = dp[i-2]+1
  else:
    dp[i] = dp[i-2]

for i in range(Q):
  l, r = list(map(int, input().split()))
  r = dp[r]
  l = dp[l-2] if 3 <= l else 0
  print(r-l)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    Q=int(input())
    prime_number=[True]*(10**5+1)
    prime_number[0]=prime_number[1]=False
    for i in range(2,int((10**5)**0.5)+1):
        if not prime_number[i]:
            continue
        for j in range(i*2,10**5+1,i):
            prime_number[j]=False
    like2017=[False]*(10**5+1)
    for i in range(1,10**5+1,2):
        if prime_number[i] and prime_number[(i+1)//2]:
            like2017[i]=True
    S=[0]*(10**5+2)
    for i in range(10**5+1):
        S[i+1]=S[i]+like2017[i]
    for _ in range(Q):
        l,r=map(int,input().split())
        print(S[r+1]-S[l])
    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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 input():
    return sys.stdin.readline().rstrip()


def main():
    # [0 is True?, 1 is True?, ..., 10000 is True?]
    table = [False for _ in range(100001)]
    for i in range(1, 100001, 2):
        table[i] = is_prime(i) and is_prime((i + 1) // 2)

    cumsum = [0 for _ in range(100001)]
    for i in range(1, 100001):
        cumsum[i] = cumsum[i - 1]
        if table[i]:
            cumsum[i] += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
q = int(input())
a = [list(map(int, input().split())) for i in range(q)]
s = [0]*(2*10**5+2)
s[3] = 1
for i in range(3, 10**5):
    for j in range(2, int((2*i)**0.5)+2):
        if (i > j and i % j == 0) or (2*i-1) % j == 0:
                b = 0
                break
    else:
        b = 1
    s[2*i-1] = b
S = [0]
for i in range(1, 10**5+1):
    c = S[i-1] + s[i]
    S.append(c)
for i in range(q):
    print(S[a[i][1]] - S[a[i][0]-1])

Submission status: Accepted

Solution code:
def is_prime(q):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(5, q-1, q)*pow(7, q-1, q) == 1
  
def main():
  s = set([561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831])
  b = [5,7]
  for i in range(2,10**5):
    if i in s:
      continue
    if is_prime(i):
      b.append(i)

  a = set([2*i-1 for i in b])
  b = set(b)
  chk = sorted(tuple(a&b))

  from bisect import bisect,bisect_left
  import sys
  input = sys.stdin.readline

  q = int(input())
  for i in range(q):
    l,r = map(int,input().split())
    print(bisect(chk,r)-bisect_left(chk,l))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def SieveOfEratosthenes(n):
    f = [True] * n
    for i in range(2, int(n**0.5)+1):
        if f[i]:
            for j in range(i*i, n, i):
                f[j] = False
    return f

MAX = 10 ** 5 + 6
pn = SieveOfEratosthenes(MAX)
C = [0] * MAX
for i in range(3, MAX, 2):
    if pn[i] and pn[(i+1)//2]:
        C[i] += 1
    C[i-1] += C[i-2]
    C[i] += C[i-1]

Q = int(input())
ans = [0] * Q
for i in range(Q):
    l, r = map(int, input().split())
    ans[i] = C[r] - C[l-1]
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
def is_prime(q):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(5, q-1, q)*pow(7, q-1, q) == 1
    
s = [561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831]
b = [5,7]
for i in range(2,10**5):
  if i in s:
    continue
  if is_prime(i):
    b.append(i)

a = set([2*i-1 for i in b])
b = set(b)
chk = sorted(list(a&b))
 
from bisect import bisect,bisect_left
import sys
input = sys.stdin.readline
 
q = int(input())
for i in range(q):
  l,r = map(int,input().split())
  print(bisect(chk,r)-bisect_left(chk,l))

Submission status: Accepted

Solution code:
import math
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    while True:
        prime = min(A)
        if prime > math.sqrt(limit):
            break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        P.append(a)
    return list(P)

a = eratosthenes(100000)
b = set([2*i-1 for i in a])
a = set(a)
chk = sorted(list(a&b))

from bisect import bisect,bisect_left
import sys
input = sys.stdin.readline

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

Submission status: Accepted

Solution code:
import random
import numpy as np

def is_prime(q,k=50):
    if q == 2: return 1
    if q < 2 or q&1 == 0: return 0

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return 0
    return 1
  
chk = np.array([0]*10**5)
for i in range(10**5):
  chk[i] = is_prime(i+1,10)
  
ans = np.array([0]*10**5)
for i in range(2,10**5):
  ans[i] = chk[i]&chk[(i+1)//2]
np.cumsum(ans,out=ans)

import sys
input = sys.stdin.readline
q = int(input())
for i in range(q):
  l,s = map(int,input().split())
  print(ans[s-1]-ans[max(0,l-2)])

Submission status: Accepted

Solution code:
import random
import numpy as np

def is_prime(q,k=50):
    # q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return 1
    if q < 2 or q&1 == 0: return 0

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return 0
    return 1
  
chk = np.array([0]*10**5)
for i in range(10**5):
  chk[i] = is_prime(i+1,15)
  
ans = np.array([0]*10**5)
for i in range(2,10**5):
  ans[i] = chk[i]&chk[(i+1)//2]
np.cumsum(ans,out=ans)

import sys
input = sys.stdin.readline
q = int(input())
for i in range(q):
  l,s = map(int,input().split())
  print(ans[s-1]-ans[max(0,l-2)])

Submission status: Accepted

Solution code:
q = int(input())
k = 10**5+1
x = [0]*k
def sieve(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False
    for i in range(2, n+1):
        if prime[i]:
            for j in range(i*2, n+1, i):
                prime[j] = False
    return prime

p = sieve(k+1)
c = 0
for i in range(3, k):
    if p[i] and p[(i+1)//2]:
        c += 1
    x[i] = c

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

Submission status: Accepted

Solution code:
import numpy as np
Q = int(input())
N = 10**5
c_sum = [0 for i in range(N+2)]
#c_sum[i+1]:iまでの2017-likeな奇数の数
#エラトステネスの篩
primes = [1 for i in range(N+1)]
primes[0], primes[1] = 0, 0
for i in range(N+1):
    if primes[i] == 1:
        for j in range(2*i, N+1, i):
            primes[j] = 0
for i in range(3, N+1):
    if primes[i] == 1 and primes[int((i+1)/2)] == 1:
        c_sum[i+1] = c_sum[i] + 1
    else:
        c_sum[i+1] = c_sum[i]
for i in range(Q):
    l, r = map(int, input().split())
    r += 1
    print(c_sum[r] - c_sum[l])

Submission status: Accepted

Solution code:
# solution

import io
import sys
import math

def prime(n):
  if n==1:
    return False
  elif n==2:
    return True
  else:
    for i in range(2,int((n)**(1/2))+1):
      if n%i==0:
        return False
    return True

list=[True]*100001

for i in range(1,100001):
  if not prime(i):
    list[i]=False

list1=[0]

count=0

for i in range(1,100001):
  if i%2==1:
    if list[i] and list[(i+1)//2]:
      count+=1
  list1.append(count)

n=int(input())

for i in range(n):
  a,b=map(int,input().split())
  print(list1[b]-list1[a-1])

Submission status: Accepted

Solution code:
def eratos(n):
    isPrime = [True]*(n+1)
    isPrime[0] = isPrime[1] = False
    for i in range(3,n+1,2):
        if isPrime[i]:
            for j in range(2*i,n+1,i): isPrime[j] = False
    for i in range(4,n+1,2): isPrime[i] = False
    return isPrime

def isLikeNum(x):
    if x%2 == 0: return False
    if isPrime[x] and isPrime[(x+1)//2]: return True
    else: return False

q = int(input())
l = [0]*q
r = [0]*q
for i in range(q):
    x,y = map(int,input().split())
    l[i] = x
    r[i] = y
m = max(r)
isPrime = eratos(m)
cnt = [0]*(m+1)
for i in range(3,m+1):
    cnt[i] = cnt[i-1]
    if isLikeNum(i): cnt[i] += 1
for i in range(q): print(cnt[r[i]]-cnt[l[i]-1])

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

Q = iin()
L = []
R = []
for i in range(Q):
    l,r = imn()
    L.append(l)
    R.append(r)    

is_primes = sieves_of_e(10**5+1)

s = [0 for _ in range(10**5+1)]
for i in range(1, 10**5):
    s[i] = s[i-1]
    if i % 2 == 1:
        if is_primes[i] and is_primes[(i+1)//2]:
            s[i] = s[i-1]+1

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

Submission status: Accepted

Solution code:
INF = 10 ** 10
q=int(input())
M=100000

def erato(n):
    primes = [0] * 2 + [1] * (n - 1)
    for i in range(4,n + 1,2):
        primes[i] = 0
    for i in range(3,n + 1,2):
        if i * i > n:
            break
        if primes[i]:
            for j in range(i * i,n + 1,i):
                primes[j] = 0

    ret = []
    for i in range(2,n + 1):
        if primes[i]:
            ret.append(i)
    return ret

prime=erato(M)
cnt=[0]*M
for i in range(len(prime)):
  cnt[prime[i]]+=0.6
  if 2*prime[i]-1<M:
    cnt[2*prime[i]-1]+=0.6
 
for i in range(1,M):
  if cnt[i]>1:
    cnt[i]=cnt[i-1]//1+1
  else:
    cnt[i]=cnt[i-1]//1
    
#print(cnt)
for i in range(q):
  l,r=map(int,input().split())
  print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
Q = int(input())

def is_prime(n):
    if n == 1: return False
    for k in range(2, int(n**0.5)+1):
        if n % k == 0:
            return 0
    return n

prime_numbers = [is_prime(i) for i in range(2, 10**5 + 1) if is_prime(i) != 0]
same = [0]*(10**5 + 1)
for n in prime_numbers:
    if (n+1) // 2 in prime_numbers:
        same[n] += 1

for i in range(10**5):
    same[i+1] += same[i]

ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    N = same[r] - same[l-1]
    ans.append(N)

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

Submission status: Accepted

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

def is_prime(n):
    if n == 1: return False
    for k in range(2, int(n**0.5)+1):
        if n % k == 0:
            return 0
    return n

prime_numbers = [is_prime(i) for i in range(2, 10**5 + 1) if is_prime(i) != 0]
# print(prime_numbers)
same = [0]*(10**5 + 1)
for n in prime_numbers:
    # print(n)
    if (n+1) // 2 in prime_numbers:
        same[n] += 1
# print(same)
# print(same[:20])

for i in range(10**5):
    same[i+1] += same[i]
# print(same[:20])
# print(same[3], same[5])
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    N = same[r] - same[l-1]
    # if same[l] != same[l-1] or same[r] != same[r-1]:
    #     N += 1
    #     if l == r:
    #         N += 1
    ans.append(N)

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

Submission status: Accepted

Solution code:
import bisect

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

Primes = primes(10 ** 5)
Ans = []
for i in Primes:
    if (i + 1) // 2 in Primes:
        Ans.append(i)

Q = int(input())
for _ in range(Q):
    l, r = map(int,input().split())
    l_index = bisect.bisect_left(Ans, l)
    r_index = bisect.bisect_right(Ans, r)
    print(r_index - l_index)

Submission status: Accepted

Solution code:
Q = int(input())
is_prime = [True for i in range(10**5+1)]
is_prime[0], is_prime[1] = False, False
for i in range(2, 10**5+1):
    if is_prime[i]:
        for j in range(i*2, 10**5+1, i):
            is_prime[j] = False
s = [0] * (10**5+1)
for i in range(1, 10**5):
    s[i+1] = s[i] + int(is_prime[i] and is_prime[(i+1)//2])
for _ in range(Q):
    left, right = map(int, input().split())
    print(s[right+1]-s[left])

Submission status: Accepted

Solution code:
Q = int(input())
is_prime = {i:True for i in range(10**5+1)}
is_prime[0], is_prime[1] = False, False
for i in range(2, 10**5+1):
    if is_prime[i]:
        for j in range(i*2, 10**5+1, i):
            is_prime[j] = False
s = [0] * (10**5+1)
for i in range(1, 10**5):
    s[i+1] = s[i] + int(is_prime[i] and is_prime[(i+1)//2])
for _ in range(Q):
    left, right = map(int, input().split())
    print(s[right+1]-s[left])

Submission status: Accepted

Solution code:
import math

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

Q = int(input())
s = [0] * (10**5+1)
for i in range(1, 10**5):
    s[i+1] = s[i] + int(is_prime(i) and is_prime((i+1)//2))
for _ in range(Q):
    left, right = map(int, input().split())
    print(s[right+1]-s[left])

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

# nまでの自然数が素数かどうかを表すリストを返す
# Sieve of Eratosthenes
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime

q = int(input())
lr = mylistinput(q)


ls = makePrimeChecker(10**5)

ls_s = [0]*(10**5)
count = 0
for i in range(len(ls_s)): 
    if i%2==0:
        pass
    else:
        if ls[i]:
            j = (i+1)//2
            if ls[j]:
                count += 1
    ls_s[i] = count
# print(ls_s[:20])

for i in range(q):
    l = lr[i][0]
    r = lr[i][1]
    ans = ls_s[r] - ls_s[l-1]
    print(ans)

Submission status: Accepted

Solution code:
def eratos(n):
    isPrime = [True]*(n+1)
    isPrime[0] = isPrime[1] = False
    for i in range(3,n+1,2):
        if isPrime[i]:
            j = i+i
            while j <= n:
                isPrime[j] = False
                j += i
    for i in range(4,n+1,2): isPrime[i] = False
    return isPrime

def isLikeNum(x):
    if x%2 == 0: return False
    if isPrime[x] and isPrime[(x+1)//2]: return True
    else: return False

q = int(input())
l = [0]*q
r = [0]*q
for i in range(q):
    x,y = map(int,input().split())
    l[i] = x
    r[i] = y
m = max(r)
isPrime = eratos(m)
cnt = [0]*(m+1)
for i in range(3,m+1):
    cnt[i] = cnt[i-1]
    if isLikeNum(i): cnt[i] += 1
for i in range(q): print(cnt[r[i]]-cnt[l[i]-1])

Submission status: Accepted

Solution code:
def eratos(n):
    isPrime = [True]*(n+1)
    isPrime[0] = isPrime[1] = False
    for i in range(3,n+1,2):
        if isPrime[i]:
            j = i+i
            while j <= n:
                isPrime[j] = False
                j += i
    for i in range(4,n+1,2): isPrime[i] = False
    return isPrime

def isLikeNum(x):
    if x%2 == 0: return False
    if isPrime[x] and isPrime[(x+1)//2]: return True
    else: return False

q = int(input())
l = [0]*q
r = [0]*q
for i in range(q):
    x,y = map(int,input().split())
    l[i] = x
    r[i] = y
m = max(r)
isPrime = eratos(m)
cnt = [0]*(m+1)
for i in range(3,m+1):
    if isLikeNum(i):
        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:
def divisor_num(x):
    num = 0
    for i in range(1,int(x**0.5)+1):
        num += (x%i == 0)*2
    num -= (x**0.5).is_integer()
    return num

N = 100000

prime = [-1]*(N+1)
sim2017 = [0]*(N+1)

for i in range(N+1):
    if prime[i] == -1:
        if divisor_num(i) == 2:
            prime[i] = 1
            for j in range(2,N//i+1):
                prime[i*j] = 0
        else:
            prime[i] = 0
    
    if prime[i] == 1 and prime[(i+1)//2 ] == 1:
        sim2017[i] += 1

for i in range(N):
    sim2017[i] += sim2017[i-1]

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

Submission status: Accepted

Solution code:
import math

prime = [2]
max = 10 ** 5
limit = int(math.sqrt(max))
data = [i + 1 for i in range(2, max, 2)]

while limit > data[0]:
    prime.append(data[0])
    data = [j for j in data if j % data[0] != 0]
prime = prime + data

lista = [0] * max
for i in prime:
    if (i + 1) / 2 in prime:
        lista[i - 1] = 1

listb = [0]
for i in range(max):
    listb.append(lista[i] + listb[i])

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