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:
import math


def main():
    Q = int(input())

    N = 10 ** 5
    is_prime = eratosthenes(N)
    like_2017 = [0 for _ in range(N + 1)]
    for i in range(3, N + 1, 2):
        if is_prime[i] and is_prime[(i + 1) // 2]:
            like_2017[i] = 1
    for i in range(3, N + 1):
        like_2017[i] += like_2017[i - 1]

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


def eratosthenes(N):
    """エラトステネスの篩"""
    is_prime = [True for _ in range(N + 1)]
    is_prime[0] = False
    is_prime[1] = False
    max_prime = int(math.sqrt(N))
    for n in range(2, max_prime + 1):
        if is_prime[n]:
            # n-1までは判定済みのため除外されている
            # => max_prime導入も同じ理由
            for i in range(n * n, N + 1, n):
                is_prime[i] = False
    return is_prime

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
Q = int(input())
P = [2]
PF = [False for _ in range(100001)]
PF[2] = True
SUM = [0, 0, 0]
sum_val = 0
for i in range(3, 100001):
	if not i % 2 == 0:
		is_p = True
		for p in P:
			if i % p == 0:
				is_p = False
				break
		if is_p:
			if i < 317:
				P.append(i)
			PF[i] = True
			if PF[(i + 1) // 2]:
				sum_val += 1
	SUM.append(sum_val)
ans = []
for _ in range(Q):
	l, r = map(int, input().split())
	ans.append(SUM[r] - SUM[l - 1])	
[print(i) for i in ans]

Submission status: Accepted

Solution code:
import math
import sys

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False

q = input()
lr = []
max_num = 0
INF = sys.maxint
input_list = sieve_of_erastosthenes(100000)
# prime_list = [i for i, b in enumerate(input_list) if b == True]
prime_list_append = []
sum_count = 0
for index, i in enumerate(input_list):
    if i and input_list[(index + 1) / 2]:
        # print i, (index + 1)/2, sum_count
        sum_count += 1
        prime_list_append.append(sum_count)
    else:
        prime_list_append.append(sum_count)

for ii in xrange(q):
    tmp = map(int, raw_input().split(" "))
    # count = 0
    # for j in prime_list_append[tmp[0]:tmp[1]]:
    #     count += 1
    print prime_list_append[tmp[1]] - prime_list_append[tmp[0]-1]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
u = 100000

f = [False]*(u+1)
for i in range(2, u+1):
    if not f[i]:
        for j in range(i+i, u+1, i):
            f[j] = True

c = [0]*(u+2)
for i in range(3, u+1, 2):
    if not f[i] and not f[int((i+1)/2)]:
        c[i] += 1
for i in range(3, u+1):
    c[i] += c[i-1]

q = int(input())
for i in range(q):
    s, e = map(int, input().split())
    print(c[e] - c[s-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    elif primes[i]:
        primes[i * 2::i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
cumsum = np.cumsum(like2017)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print(cumsum[r] - cumsum[l - 1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    else:
        primes[i * 2::i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
cumsum = np.cumsum(like2017)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print(cumsum[r] - cumsum[l - 1])

Submission status: Accepted

Solution code:
def prime_TorF(n):
    p = [True for i in range(n)]
    p[0] = p[1] = False
    for i in range(2, 100000):
        if p[i]:
            for j in range(2 * i, 100000, i):
                p[j] = False

    return p


def solve():
    q = int(input())
    l, r = [], []
    for _ in range(q):
        tmp_l, tmp_r = list(map(int, input().split(" ")))
        l.append(tmp_l)
        r.append(tmp_r)

    p = prime_TorF(100000)

    s = [0 for i in range(100000)]
    for i in range(1, 100000, 2):
        if p[i] and p[(i + 1) // 2]:
            s[i] = 1

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

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


solve()

Submission status: Accepted

Solution code:
def solve():
    q = int(input())
    l, r = [], []
    for _ in range(q):
        tmp_l, tmp_r = list(map(int, input().split(" ")))
        l.append(tmp_l)
        r.append(tmp_r)

    p = [True for i in range(100000)]
    p[0] = p[1] = False
    for i in range(2, 100000):
        if p[i]:
            for j in range(2 * i, 100000, i):
                p[j] = False

    s = [0 for i in range(100000)]
    for i in range(1, 100000, 2):
        if p[i] and p[(i + 1) // 2]:
            s[i] = 1

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

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


solve()

Submission status: Accepted

Solution code:
N = 100010

p = [True for i in range(N)]
p[0]=p[1]=False
for i in range(2,N):
    if p[i]:
        for j in range(2*i,N,i):
            p[j] = False

s = [0 for i in range(N)]
for i in range(1,N,2):
    if p[i] and p[(i+1)//2]:
        s[i] = 1

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

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

Submission status: Accepted

Solution code:
n=[True]*100001
n[0]=n[1]=False
for i in range(2,317):
  if n[i]:
    for j in range(i**2,100000,i):
      n[j]=False
c=[0]*100002
for i in range(3,100001):
  c[i]=c[i]+c[i-1]
  if i%2==1 and n[i] and n[int((i+1)/2)]:
    c[i]=c[i]+1
for i in range(int(input())):
  a=input().split(' ')
  print(c[int(a[1])]-c[int(a[0])-1])

Submission status: Accepted

Solution code:
n=[True]*100001
n[0]=n[1]=False
for i in range(2,317):
  if n[i]:
    for j in range(i**2,100000,i):
      n[j]=False
c=[0]*100002
for i in range(3,100001,2):
  if n[i] and n[int((i+1)/2)]:
    c[i]=c[i]+1
for i in range(3,100001):
  c[i]=c[i]+c[i-1]
for i in range(int(input())):
  a=input().split(' ')
  print(c[int(a[1])]-c[int(a[0])-1])

Submission status: Accepted

Solution code:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

for i in range(3, 100001):
  c[i] = c[i] + c[i-1]

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Submission status: Accepted

Solution code:
import math

tb = [0 for x in range(10**5 + 1)]
so = []
sof = [False for x in range(len(tb))]
for i in range(2, 10**5 + 1):
  flag = True
  for s in so:
    if i % s == 0:
      flag = False
      break
    if s > math.sqrt(i):
      break
  if flag:
    so += [i]
    sof[i] = True

count = 0
for i in range(3, 10**5 + 1):
  if sof[i]:
    n2 = (i + 1) // 2
    if sof[n2]:
      count += 1
  tb[i] = count

q = int(input())
L = []
r = []
for i in range(q):
  L += [0]
  r += [0]
  L[i], r[i] = [int(x) for x in input().split()]
for i in range(q):
  res = tb[r[i]] - tb[L[i] - 1]
  print(res)

Submission status: Accepted

Solution code:
import math
Q=int(input())
N=10**5+1

L = []
R = []
for i in range(Q):
    ll,rr=[int(i) for i in input().split()]
    L.append(ll)
    R.append(rr)

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

is_prime = is_prime_list(N)
nita = [0]*N
for i in range(N):
    if is_prime[i] == True and is_prime[(i+1)//2] == True:
        nita[i] = nita[i-1] + 1
    else:
        nita[i] = nita[i-1]
#print(nita)
for i in range(Q):
    a = nita[R[i]] - nita[L[i]-1]
    print(a)

Submission status: Accepted

Solution code:
q = int(input())

def eratosthenes(n):
    l = [True] * (n+1)
    l[2] = True
    for i in range(2, n+1):
        if l[i]:
            for j in range(i*i, n+1, i):
                l[j] = False
    return l

l = eratosthenes(10**5)
r = [0] * (10**5 + 1)
r[1] = r[2] = 0
for i in range(3,10**5):
    if i % 2 == 0:
        r[i] = r[i-1]
    elif l[i] and l[(i+1) // 2]:
        r[i] = r[i-1] + 1
    else:
        r[i] = r[i-1]
for i in range(q):
    a, b = map(int, input().split())
    print(r[b] - r[a-1])

Submission status: Accepted

Solution code:
primes = [True]*100000
for i in range(2,100000):
  if primes[i] == False:
    continue
  for j in range(2*i, 100000, i):
    primes[j] = False

c = [0]*100000

for i in range(3,100000):
  if primes[i] and primes[(i+1)//2] == True:
    c[i] = c[i-1]+1
  else:
    c[i] = c[i-1]


q = int(input())
ran = []
for i in range(q):
  ran.append(list(map(int, input().split())))
for i in range(q):
  print(c[ran[i][1]]-c[ran[i][0]-1])