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:
elst = [True for _ in range(10**5+2)]
elst[0] = False
elst[1] = False

for i, e in enumerate(elst):
  if e:
    for j in range(2 * i, 10**5+2, i):
      elst[j] = False

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

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

Submission status: Accepted

Solution code:
# D
from math import sqrt
def sieve(n:int)->list:
    """エラトステネスの篩"""
    if n<2:  return [False]*(n+1)
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(sqrt(n))+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    
    return is_prime


N = int(1e5)
is_prime = sieve(N)
# like-2017
cnt = [0]*(N+1)
for i in range(1, N+1):
    cnt[i] += cnt[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt[i] += 1
    
import sys
Q = sys.stdin.readline()
for l,r in (map(int, line.split()) for line in sys.stdin.readlines()):
    print(cnt[r] - cnt[l-1])

Submission status: Accepted

Solution code:
# D
from math import sqrt
def sieve(n:int)->list:
    """エラトステネスの篩"""
    if n<2:  return [False]*(n+1)
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(sqrt(n))+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    
    return is_prime


N = int(1e5)
is_prime = sieve(N)
# like-2017
cnt = [0]*(N+1)
for i in range(1, N+1):
    cnt[i] += cnt[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt[i] += 1
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
# D
N = 10**5
primes = set([])
is_prime = [True]*(N+2)
is_prime[0] = False
is_prime[1] = False
for i in range(2, N+2):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, N//i+1):
            is_prime[j*i] = False
    
# like-2017
cnt = [0]*(N+2)
for i in range(1, N+2):
    cnt[i] += cnt[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt[i] += 1
#print(cnt[:100])
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
# D
N = 10**5
primes = set([])
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, N+1):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, N//i+1):
            is_prime[j*i] = False
    
# like-2017
cnt = [0]*(int(1e5)+2)
for p in primes:
    if (p+1)//2 in primes:
        cnt[p] = 1
for i in range(1, int(1e5)+2):
    cnt[i] += cnt[i-1]
#print(cnt[:100])
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
primes = set([])
n = 10**5
is_prime = [True]*(n+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, n+1):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, n//i+1):
            is_prime[j*i] = False
# DP[i] = i以下の2017 likeな数
DP = [0]*(n+1)
for i in range(1, n+1):
    if i in primes and (i+1)//2 in primes:
        DP[i] = DP[i-1] + 1
    else:
        DP[i] = DP[i-1]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(DP[r] - DP[l-1])

Submission status: Accepted

Solution code:
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]
prime = [True for _ in range(10**5 + 1)]
prime[0] = prime[1] = False
for i in range(2, 320):
    if prime[i]:
        for j in range(i * 2, 10 ** 5 + 1, i):
            prime[j] = False
counter = [0 for _ in range(10 ** 5 + 1)]
for i in range(1, 10 ** 5 + 1):
    if prime[i] and prime[(i + 1) // 2]:
        counter[i] = counter[i - 1] + 1
    else:
        counter[i] = counter[i - 1]
for q in query:
    l, r = q
    print(counter[r] - counter[l - 1])

Submission status: Accepted

Solution code:
def sieve(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]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    table = [ i for i in range(n+1) if is_prime[i]]
    return table, is_prime

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

prime, flag = sieve(10 ** 5)
number = [0 for i in range(10 ** 5+1)]

for i in range(2, 10 ** 5):
    if flag[i] and flag[(i+1)//2]:
        number[i] += 1
        
for i in range(1, 10 ** 5):
    number[i] += number[i-1]
        
result = []
            
for i in range(N):
    res = number[L[i][1]] - number[L[i][0]-1]
    result.append(res)

for res in result:
    print(res)

Submission status: Accepted

Solution code:
is_prime = [True]*100001
is_prime[0] = False
is_prime[1] = False
for i in range(2,int(100000**0.5)+1):
  if not is_prime[i]:
      continue
  for j in range(i*2,100001,i):
      is_prime[j] = False
S = [0]*100001
for N in range(3,100001,2):
  if is_prime[N] and is_prime[(N+1)//2]:
    S[N] += 1
for N in range(3,100001):
    S[N] += S[N-1]
Q = int(input())
for k in range(Q):
  l,r = map(int,input().split())
  print(S[r]-S[l-1])

Submission status: Accepted

Solution code:
n=10**5;p=[0,0]+[1]*~-n
for i in range(2,int(n**0.5)+1):
 if p[i]:
  for j in range(i*2,n+1,i):p[j]=0
c=[0]
for i in range(1,n+1):c.append(c[-1]+(i%2and p[i]and p[-~i//2]))
for _ in[0]*int(input()):l,r=map(int,input().split());print(c[r]-c[l-1])

Submission status: Accepted

Solution code:
n=10**5
p=[0,0]+[1]*~-n
for i in range(2,int(n**0.5)+1):
  if not p[i]:continue
  for j in range(i*2,n+1,i):p[j]=0
c=[0]
for i in range(1,n+1):
  c.append(c[-1]+(i%2and p[i]and p[-~i//2]))
for _ in range(int(input())):
  l,r=map(int,input().split())
  print(c[r]-c[l-1])

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple


def next_str() -> str:
    result = ""
    while True:
        tmp = sys.stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != "\r":
            break
    return result


def next_int() -> int:
    return int(next_str())


query = namedtuple('qry', ('l', 'r'))
Q = next_int()
queries = [query(next_int(), next_int()) for i in range(Q)]
right = -sys.maxsize
left = sys.maxsize


def is_prime(n: int) -> bool:
    if n < 2:
        return False
    i = 2
    while i ** 2 <= n:
        if n % i == 0:
            return False
        i += 1
    return True


def main() -> None:
    global left, right
    for q in queries:
        left = min(left, q.l)
        right = max(right, q.r)

    dp = [0] * ((right - left) // 2 + 1)

    for i in range(left, right + 1, 2):
        j = (i - left) // 2
        if j != 0:
            dp[j] = dp[j - 1]
        if is_prime(i) and is_prime((i + 1) // 2):
            dp[j] += 1

    for q in queries:
        ans = 0
        ans += dp[(q.r - left) // 2]
        if q.l != left:
            ans -= dp[(q.l - left) // 2 - 1]

        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import itertools
 
def prime_boolean_table(n):
    primes=[True]*(n+1)
    primes[0]=False
    primes[1]=False
    limit=math.floor(math.sqrt(n)+1)
    for i in range(2,limit+1):
        if primes[i]:
            for j in range(i*2,n+1,i):
                primes[j]=False
    return primes

n=10**5
q=int(input())
a=[list(map(int,input().split())) for _ in range(q)]
primes=prime_boolean_table(10**5)
c=[0]*(n+1)
for i in range(n):
    if primes[i+1] and primes[(i+2)//2]:
        c[i+1]=c[i]+1
    else:
        c[i+1]=c[i]
for i in range(q):
    ans=c[a[i][1]]-c[a[i][0]-1]
    print(ans)

Submission status: Accepted

Solution code:
def binary_search_loop(li,n):
    arry = li
    target = n
    result = None
    left = 0
    right = len(arry) - 1

    while left <= right:
        mid = (left + right) // 2
        if arry[mid] == target:
            result = mid
            break               
        elif arry[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    if result == None:
        return False
    else:
        return True

        
def era(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(2*i, n + 1, i):
                table[j] = 1
    
    return prime_list

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



N = 10**5
prime_list = era(N)
#2M-1(Mは素数)と表される素数の累積和
ruiseki = [0]*(N+1)

for i in prime_list:
    if 2*i - 1 <= N:
        if binary_search_loop(prime_list,2*i - 1):
            ruiseki[2*i - 1] = 1   

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


for i in s:
    print(ruiseki[i[1]] - ruiseki[i[0]-1])

Submission status: Accepted

Solution code:
N = 100001
pr = [True]*(N+1)
c = [0]*(N+1)
pr[0] = pr[1] = False
for i in range(2,N) :
    if pr[i]:
        for j in range(i+i,N,i):
            pr[j] = False

for i in range(3,N,2):
    if pr[i] and pr[(i+1)//2]:
        c[i]+=1
for i in range(3,N):
    c[i]+=c[i-1]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(c[r]-c[l-1])

Submission status: Accepted

Solution code:
import itertools

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

def main():
    pl = prime_boolean_table(10**5)
    ql = [0]*(10**5+1)
    for i in range(1,10**5+1):
        if pl[i] and pl[(i+1)//2]:
            ql[i] += 1
    ql = list(itertools.accumulate(ql))
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        print(ql[r]-ql[l-1])

if __name__=='__main__':
    main()

Submission status: Accepted

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

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

def main():
    pl = prime_boolean_table(10**5)
    ql = [0]*(10**5+1)
    for i in range(1,10**5+1):
        if pl[i] and pl[(i+1)//2]:
            ql[i] += 1
    ql = list(itertools.accumulate(ql))
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        print(ql[r]-ql[l-1])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

pl = prime_boolean_table(10**5)
ql = [0]*(10**5+1)
for i in range(1,10**5+1):
    if pl[i] and pl[(i+1)//2]:
        ql[i] += 1
ql = list(itertools.accumulate(ql))
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    print(ql[r]-ql[l-1])

Submission status: Accepted

Solution code:
from itertools import accumulate

N = 100000
prime = [True]*(N+1)

prime[0] = prime[1] = False

for i in range(N+1):
    if prime[i]:
        for j in range(2*i, N+1, i):
            prime[j] = False

prime2 = [0] * (N+1)

for i in range(N+1):
    if prime[i] and prime[(i+1)//2]:
        prime2[i] = 1

acc = list(accumulate(prime2))

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

Submission status: Accepted

Solution code:
def isPrime(i):
    if i < 2:
        return False
    elif i == 2:
        return True
    elif i % 2 == 0:
        return False
    for j in range(3, int(i**0.5)+1, 2):
        if i % j == 0:
            return False
    return True

def inpl(): return list(map(int, input().split()))

Q = int(input())
# query = [inpl() for i in range(Q)]
N = 10 ** 5


prime = [True] * (N+1)
prime[0] = False
prime[1] = False
for i in range(2, N+1):
    if prime[i] is False:
        continue
    
    tmp = i * 2
    while tmp <= N:
        prime[tmp] = False
        tmp += i

dst = [0] * (N+1)
for i in range(1, N+1):
    dst[i] = dst[i-1] + int(prime[i] and prime[(i+1)//2])

# print(rsq.tree[rsq.bottom:rsq.bottom+10])
for _ in range(Q):
    l, r = inpl()
    print(dst[r]-dst[l-1])

Submission status: Accepted

Solution code:
def prime_table(m):
    t = [True] * (m + 1)
    i = 2
    while i * i <= m:
        if t[i]:
            j = i + i
            while j <= m:
                t[j] = False
                j += i
        i += 1
    return t



Q = int(input())
pt = prime_table(10 ** 5)
sn = [False] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    sn[i] = pt[i] and pt[(i + 1) // 2]
c = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    c[i] = c[i - 2] + (1 if sn[i] else 0)
    # print(i, c[i])
for _ in range(Q):
    l, r = map(int, input().split())
    print(c[r] - c[l - 2])

Submission status: Accepted

Solution code:
def prime_table(m):
    t = [True] * (m + 1)
    i = 2
    while i * i <= m:
        if t[i]:
            j = i + i
            while j <= m:
                t[j] = False
                j += i
        i += 1
    return t
    # t[i] = i が素数ならTrue


Q = int(input())
pt = prime_table(10 ** 5)
sn = [False] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    sn[i] = pt[i] and pt[(i + 1) // 2]
c = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    c[i] = c[i - 2] + (1 if sn[i] else 0)
    # print(i, c[i])
for _ in range(Q):
    l, r = map(int, input().split())
    print(c[r] - c[l - 2])

Submission status: Accepted

Solution code:
# TLEするっぽいなー
Q = int(input())
LR = [tuple(map(int,input().split())) for _ in range(Q)]

N = 100010
# まずは素数列挙
P = []
A = [True]*N
for i in range(2,N):
    if A[i]:
        P.append(i)
        j = 2
        while i*j < N:
            A[i*j] = False
            j += 1

# 整数iまでの「2017数」を数える
Ans = [0]*N
for p in P:
    if p==2:
        continue
    if (p+1)//2 in P:
        Ans[p] = 1

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate
N = 100000
prime = [True for _ in range(N+1)]
prime[0] = False
prime[1] = False
i = 2
for i in range(N+1):
    if prime[i]:
        for j in range(2*i, N+1, i):
            prime[j] = False

prime2 = [1 if prime[i] and prime[(i+1)//2] else 0 for i in range(N+1)]
acc = list(accumulate(prime2))

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

Submission status: Accepted

Solution code:
from itertools import accumulate
N = 100000
prime = [True for _ in range(N+1)]
prime[0] = False
prime[1] = False
i = 2
for i in range(N+1):
    if prime[i]:
        for j in range(2*i, N+1, i):
            prime[j] = False
prime2 = [0 for _ in range(N+1)]
for i in range(N+1):
    if prime[i] and prime[(i+1)//2]:
        prime2[i] = 1
acc = list(accumulate(prime2))

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

Submission status: Accepted

Solution code:
Q = int(input().strip())

NUMS = 100000
fs = [True] * (NUMS + 1)
cs = [0] * (NUMS + 1)

for i in range(2,int(pow(NUMS,0.5))):
    if fs[i]:
        for j in range(i + i, NUMS,i):
            fs[j] = False
for i in range(3,NUMS,2):
    if fs[i] and fs[int((i + 1) / 2)]:
        cs[i] += 1
for i in range(3,NUMS):
    cs[i] += cs[i - 1]

for i in range(0,Q):
    l,r = map(int,input().strip().split())
    print(cs[r] - cs[l - 1])

Submission status: Accepted

Solution code:
Q = int(input().strip())

NUMS = 100000
fs = [True] * (NUMS + 1)
cs = [0] * (NUMS + 1)

for i in range(2,NUMS):
    if fs[i]:
        for j in range(i + i, NUMS,i):
            fs[j] = False
for i in range(3,NUMS,2):
    if fs[i] and fs[int((i + 1) / 2)]:
        cs[i] += 1
for i in range(3,NUMS):
    cs[i] = cs[i] + cs[i - 1]

for i in range(0,Q):
    l,r = map(int,input().strip().split())
    print(cs[r] - cs[l - 1])

Submission status: Accepted

Solution code:
def get_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 set([i for i in range(n + 1) if is_prime[i]])


def solve():
    # A = [int(n) for n in input().split()]

    NMAX = 100000
    primes = set(get_primes(NMAX+1))
    table = [0] * NMAX

    for n in range(1, NMAX):
        table[n] = table[n-1] + int(n in primes and (n+1)//2 in primes)

    Q = int(input())
    for _ in range(Q):
        l, r = [int(x) for x in input().split()]
        print(table[r]-table[l-1])
    
    return 0


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        na = list(map(int, input().split()))
        l.append(na[0])
        r.append(na[1])

    r_max = 100000
    primes = [True for i in range(r_max)]
    like_numbers = [0 for i in range(r_max)]

    primes[0] = primes[1] = False
    max_i = int(math.sqrt(r_max))
    i = 2
    while i <= max_i:
        primes[i] = True
        for j in range(i * i, r_max, i):
            primes[j] = False
        while i <= max_i:
            i += 1
            if primes[i]:
                break

    for i in range(3, r_max, 2):
        if primes[i] and primes[int((i + 1) / 2)]:
            like_numbers[i] = 1

    c = 0
    for i in range(3, r_max, 2):
        if like_numbers[i]:
            c += 1
        like_numbers[i] = c


    for i in range(Q):
        if l[i] == 1:
            print(like_numbers[r[i]])
        else:
            print(like_numbers[r[i]] - like_numbers[l[i] - 2])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from math import sqrt

# 素数判定用関数
def is_prime2(num):
    if num < 2:
        return False
    if num == 2 or num == 3 or num == 5:
        return True
    if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
        return False
    # 疑似素数(2でも3でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    num_sqrt = sqrt(num)
    while prime <= num_sqrt:
        if num % prime == 0:
            return False
        prime += step
        step = 6 - step
    return True

# 同じ数2回素数判定やりたくないのでここに保存
prime = [is_prime2(i) for i in range(100001)]
# 2017に似た数
like2017 = [0] * 100001
for i in range(1, 100001, 2):
    if prime[i] and prime[(i+1)//2]:
        like2017[i] = 1
# 累積和
sm = [0] * 100001
for i in range(1, 100001):
    sm[i] = sm[i-1] + like2017[i]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    # 累積和から各QはO(1)で出せる
    print(sm[r]-sm[l-1])

Submission status: Accepted

Solution code:
like2017s = [
    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
]
cumsum = [0] * 100001
for l in like2017s:
    cumsum[l] = 1
for i in range(1, 100001):
    cumsum[i] += cumsum[i - 1]

Q = int(input())
LR = [[int(_) for _ in input().split()] for _ in range(Q)]
for l, r in LR:
    print(cumsum[r] - cumsum[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]


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

like_2017 = list(accumulate(like_2017))

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

Submission status: Accepted

Solution code:
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


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


primes = []
for i in range(2, 10 ** 5 + 1):
    if is_prime(i):
        primes.append(i)

like_2017 = []
count = [0 for _ in range(10 ** 5)]
for i in range(len(primes)):
    if binarySearch(primes, primes[i] * 2 - 1):
        like = 2 * primes[i] - 1
        count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print(count[lr[i][1]] - count[lr[i][0] - 1])

Submission status: Accepted

Solution code:
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


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


primes = []
for i in range(2, 10 ** 5 + 1):
    if is_prime(i):
        primes.append(i)

like_2017 = []
for i in range(len(primes)):
    if binarySearch(primes, primes[i] * 2 - 1):
        like_2017.append(2 * primes[i] - 1)

count = [0 for _ in range(10 ** 5)]
for like in like_2017:
    count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print(count[lr[i][1]] - count[lr[i][0]-1])