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:
maxnum = 100000

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

like_sum = [0] * maxnum
for i in range(3, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        like_sum[i] += 1

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

Submission status: Accepted

Solution code:
maxnum = 100000

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

is_like = [False] * maxnum
for i in range(maxnum):
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        is_like[i] =  True

like_sum = [0] * maxnum
for i in range(3, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_like[i]):
        like_sum[i] += 1

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

Submission status: Accepted

Solution code:
from itertools import accumulate

# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(n):
    s = [True] * n
    for x in range(2, int(n ** 0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0, n) if s[i] and i > 1]


Prime = set(eratosthenes(10**5 + 1))
Target = [0] * (10**5 + 1)
for n in range(1, 10**5 + 1):
    if n in Prime and (n + 1) / 2 in Prime:
        Target[n] = 1

Target = list(accumulate(Target))

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

Submission status: Accepted

Solution code:
import math

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

R = [0 for k in range(100000)]
R[3] = 1
for k in range(3,100000,2):
    if P[k] and P[(k+1)//2]:
        R[k] = 1

for k in range(1,100000):
    R[k] += R[k-1]

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

Submission status: Accepted

Solution code:
def prime(n):
  l = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(n)]
  l[0] = l[1] = False
  l[2] = l[3] = l[5] = True
  sqrt = n**(1/2)
  for s in range(3,n,2):
    if s>=sqrt:
      return l
    for s in range(s**2,n,s): 
      l[s]=False

S=100001
l=prime(S)
cd=[3]+[i for i in range(5,S,4) if l[i] and l[(i+1)//2]]
size=len(cd)
m=[0 for _ in range(S)]
p=0
for i in range(S):
  if p<size and i>=cd[p]:
    p+=1
  m[i]=p

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

Submission status: Accepted

Solution code:
def sieve(n):
    '''

    :param n:
    :return: n以下の素数のリストを返す
    '''
    prime = []
    is_prime = [True] * (n + 1) #is_prime[i] = Trueならiは素数
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return is_prime

import bisect
Q = int(input())
queries = [list(map(int, input().split())) for _ in range(Q)]
primehantei = sieve(10 ** 5)
like2017 = []
for i in range(10 ** 5):
    if primehantei[i] == True and primehantei[ (i + 1) // 2] == True:
        like2017.append(i)

for i in range(Q):
    li, ri = queries[i]
    print(bisect.bisect_right(like2017, ri) - bisect.bisect_right(like2017, li - 1))

Submission status: Accepted

Solution code:
def isPrime(n):
    if n == 0 or n == 1:
        return 0
    for i in range(2, n):
        if i * i > n:
            return 1
        if n % i == 0:
            return 0
    return 1
        
N = 100010
cnt = [0] * N

for x in range(1, N):
    cnt[x] = cnt[x-1] + (isPrime(x) and isPrime((x + 1) // 2))

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
pri = []
is_pri = [1 for i in range(100005)]
is_pri[0] = is_pri[1] = 0
sm = [0] * 100005

for i in range(2, 100005):
    if is_pri[i]:
        pri.append(i)
    for j in pri:
        if i * j < 100005:
            is_pri[i * j] = 0
        if i * j >= 100005 or i % j == 0:
            break

for i in range(100005):
    if is_pri[i] and is_pri[int((i + 1) / 2)]:
        sm[i] = 1

for i in range(1, 100005):
    sm[i] += sm[i - 1]

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

Submission status: Accepted

Solution code:
Q = int(input())
def prime_table(n):
  P = [1] * (n + 1)
  P[0] = 0
  P[1] = 0
  for i in range(2, n + 1):
    if P[i]:
      for j in range(2 * i, n + 1, i):
        P[j] = 0
  return P
primes = prime_table(10 ** 5)
Like2017 = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
  if i % 2:
    Like2017[i] = primes[i] * primes[(i + 1) // 2]
  Like2017[i] += Like2017[i - 1]
for i in range(Q):
  l, r = map(int, input().split())
  print(Like2017[r] - Like2017[l - 1])

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

input = sys.stdin.readline

N = int(input())


def prime_boolean_table(n):
    primes = [True] * (n + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, n + 1):
        if primes[i]:
            for j in range(i + i, n + 1, i):
                primes[j] = False

    return primes


primes = prime_boolean_table(10**5)
A = [0] * 10**5
for i in range(1, 10**5):
    A[i] += A[i - 1]
    if primes[i] and primes[(i + 1) // 2]:
        A[i] += 1

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