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 eraP(n):
    if n<=1: return [False]*(n+1)
    elif n<=2: return [False, False, True]
    L = [False if i%2==0 or i%3==0 else True for i in range(n)]
    L[0] = False; L[1] = False;
    L[2] = True; L[3] = True; L[5]=True
    limit = math.sqrt(n)
    for i in range(3,n,2):
        if i >= limit: return L
        for s in range(i**2,n,i):
            L[s] = False
    return L

q = int(input())
LR = [[0,0] for _ in range(q)]
for i in range(q):
    LR[i] = list(map(int, input().split()))
P = eraP(pow(10,5)+1)[1:]

sumP = [0,0,0]
for i in range(2,pow(10,5)):
    sumP.append(sumP[-1]+int(P[i] and P[(i+1)//2]))

for lr in LR:
    print(sumP[lr[1]]-sumP[lr[0]-1])

Submission status: Accepted

Solution code:
import math

#素数判定
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

q = int(input())

a = [0] * (10**5 + 1)

for i in range(10**5 + 1):
    #条件を満たすなら1
    if IsPrime(i) and IsPrime((i + 1) / 2) and i % 2 == 1:
        a[i] = 1
    else:
        a[i] = 0

#先頭からの累積和をとる
for i in range(10**5):
    a[i + 1] += a[i]

#クエリ処理
for i in range(q):
    l, r = map(int, input().split())
    print(a[r] - a[l - 1])

Submission status: Accepted

Solution code:
q=int(input())
#lr=[list(map(int,input().split())) for i in  range(q)]
MAX=10**5+1
l=[0]*MAX

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
cnt=0
for i in range(1, MAX, 2):
  if is_prime(i) and is_prime((i+1)/2):
    l[i]=1
    
l2=[0]*(MAX+1)
for i in range(0, MAX):
  l2[i+1]=l2[i]+l[i]
#print(l2)

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

Submission status: Accepted

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

p = [0] * (10 ** 5)
for i in range(10**5):
    if i % 2 == 0:
        continue
    if is_prime(i) and is_prime((i+1)//2):
        p[i] = 1

acm = [0] * (10 ** 5 + 1)
for i in range(10**5):
    acm[i+1] = acm[i] + p[i]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(acm[r+1] - acm[l])

Submission status: Accepted

Solution code:
Q = int(input())
A = []
B = []
for i in range(Q):
    in1, in2 = list(map(int,input().split()))
    A.append(in1)
    B.append(in2)
    
def sieve(N):
    p = 0
    prime = []
    is_prime = [1 for _ in range(N + 1)]
    is_prime[0], is_prime[1] = 0, 0
    for i in range(2, N + 1):
        if is_prime[i]:
            p += 1
            temp = i
            prime.append(i)
            while(temp <= N):
                is_prime[temp] = 0
                temp += i
            is_prime[i] = 1
    return is_prime

p_list = sieve(10 ** 5 + 10)
acc = [0, 0]
for i in range(3, 10 ** 5 + 1, 2):
    if p_list[i] and p_list[(i + 1) // 2]:
        acc.append(acc[-1] + 1)
    else:
        acc.append(acc[-1])
for i in range(Q):
    print(acc[(B[i] + 1) // 2] - acc[(A[i] + 1) // 2 - 1])

Submission status: Accepted

Solution code:
Q = int(input())

p = [True] * (10 ** 5 + 1)
p[0] = p[1] = False
for i in range(2, 10 ** 5 + 1):
    for j in range(2 * i, 10 ** 5 + 1, i):
        p[j] = False

pp = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    pp[i] = int(p[i] and p[(i + 1) // 2]) + pp[i - 1]

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

Submission status: Accepted

Solution code:
MAX_INT = 10**5+1
primes = [True] * (10**5+1)
primes[0], primes[1] = False, False
for i in range(2, int(MAX_INT**0.5)+1):
  if primes[i]:
    for j in range(i*2, MAX_INT, i):
      primes[j] = False

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

for i in range(1, 10**5+1):
  cumsum[i] += cumsum[i-1]

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

Submission status: Accepted

Solution code:
# エラトステネスの篩, 累積和
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    j = (i + 1) // 2
    if prime_table[i] == i and prime_table[j] == j:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(input())
result = []
for _ in range(Q):
    l, r = map(int, input().split())
    result.append(cs[r] - cs[l - 1])
#print('\n'.join(str(i) for i in result))
print(*result, sep='\n')

Submission status: Accepted

Solution code:
# エラトステネスの篩, 累積和
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    j = (i + 1) // 2
    if prime_table[i] == i and prime_table[j] == j:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(input())
result = []
for _ in range(Q):
    l, r = map(int, input().split())
    result.append(cs[r] - cs[l - 1])
print('\n'.join(str(i) for i in result))
#print(*result, sep='\n')

Submission status: Accepted

Solution code:
import bisect
q = int(input())
LR = (tuple(map(int,input().split())) for i in range(q))
ans = []
sosuu = [2]
A = 100000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        if (L+1)/2 in sosuu:
          ans.append(L)
for lr in LR:
  print(bisect.bisect_right(ans,lr[1]) - bisect.bisect_left(ans,lr[0]))

Submission status: Accepted

Solution code:
import bisect
q = int(input())
LR = [tuple(map(int,input().split())) for i in range(q)]
ans = []
sosuu = set([2])
A = 100000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.add(L)
        if (L+1)/2 in sosuu:
          ans.append(L)
for lr in LR:
  print(bisect.bisect_right(ans,lr[1]) - bisect.bisect_left(ans,lr[0]))

Submission status: Accepted

Solution code:
import bisect
q = int(input())
LR = [tuple(map(int,input().split())) for i in range(q)]
ans = []
sosuu = [2]
A = 100000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        if (L+1)/2 in sosuu:
          ans.append(L)
for lr in LR:
  print(bisect.bisect_right(ans,lr[1]) - bisect.bisect_left(ans,lr[0]))

Submission status: Accepted

Solution code:
q = int(input())
is_prime = [1] * (10**5 + 1)
is_prime[0] = 0
is_prime[1] = 0
for i in range(2, 10**5+1):
    if is_prime[i] == 1:
        for j in range(i+i, 10**5+1, i):
            is_prime[j] = 0
ls = [0]
for i in range(1, 10**5+1):
    if is_prime[i] == 1 and is_prime[(i+1)//2] == 1:
        ls.append(ls[i-1]+1)
    else:
        ls.append(ls[i-1])
for i in range(q):
    l, r = map(int, input().split())
    print(ls[r] - ls[l-1])

Submission status: Accepted

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

    return is_prime


q = int(input())

p = eratosthenes(10 ** 5)
l = [0] * 10 ** 5
for i in range(3, 10 ** 5, 2):
    if p[i] and p[(i+1)//2]:
        l[i] = 1

sum_l = [0]
for v in l[1:]:
    sum_l.append(sum_l[-1] + v)

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

for v in res:
    print(v)

Submission status: Accepted

Solution code:
from bisect import bisect_left


def eratosthenes(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 is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False

    return is_prime


q = int(input())

p = eratosthenes(10 ** 5)
l = [0] * 10 ** 5
for i in range(3, 10 ** 5, 2):
    if p[i] and p[(i+1)//2]:
        l[i] = 1

sum_l = [0]
for v in l[1:]:
    sum_l.append(sum_l[-1] + v)

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

for v in res:
    print(v)

Submission status: Accepted

Solution code:
from bisect import bisect_left


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


def is_similar(n):
    pos = bisect_left(p, n)
    if pos < len(p) and p[pos] == n:
        return True
    else:
        return False


q = int(input())

p = primes(10 ** 5)
l = [0] * 10 ** 5
for i in range(3, 10 ** 5, 2):
    if is_similar(i) and is_similar((i+1)//2):
        l[i] += 1

sum_l = [0]
for v in l[1:]:
    sum_l.append(sum_l[-1] + v)

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

for v in res:
    print(v)

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

# 2017数 かどうかのマップ
data = [0] * 10**5
# 処理系
for i in range(1, 10**5 + 1):
    if is_prime(i) and is_prime((i+1)//2):
        data[i-1] = 1

cumulative_sum = [0] * 10**5
cumulative_sum[0] = data[0]
for i in range(10**5 - 1):
    cumulative_sum[i+1] += cumulative_sum[i] + data[i+1]

# s_0 = 0 となるように
cumulative_sum = [0] + cumulative_sum

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(cumulative_sum[r] - cumulative_sum[l-1])
    # print(sum(data[l:r+1]))

Submission status: Accepted

Solution code:
# エラトステネスの篩, 累積和
def make_prime_table(N):
    sieve = list(range(N + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(N ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, N + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    j = (i + 1) // 2
    if prime_table[i] == i and prime_table[j] == j:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(input())
result = []
for _ in range(Q):
    l, r = map(int, input().split())
    result.append(cs[r] - cs[l - 1])
print('\n'.join(str(i) for i in result))

Submission status: Accepted

Solution code:
# エラトステネスの篩, 累積和
def make_prime_table(N):
    sieve = list(range(N + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(N ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, N + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(input())
result = []
for _ in range(Q):
    l, r = map(int, input().split())
    result.append(cs[r] - cs[l - 1])
print('\n'.join(str(i) for i in result))

Submission status: Accepted

Solution code:
# エラトステネスの篩, 累積和
def make_prime_table(N):
    sieve = [0] * (N + 1)
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, N + 1):
        if sieve[i] != 0:
            continue
        sieve[i] = i
        for j in range(i * i, N + 1, i):
            if sieve[j] == 0:
                sieve[j] = i
    return sieve

max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

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

Submission status: Accepted

Solution code:
#import numpy

#for loop
#a = [1,2,3,4,5,6,7,8,9,10]
#s = [0]*len(a)
#s[0] = a[0]
#for i in range(len(a)-1):
#  s[i+1] = s[i] + a[i+1]
#print(s)

#numpy.cumsum()
#print(numpy.cumsum(a))

q = int(input())
n = 10**5+1
limit = int(n**0.5)
a = [i for i in range(3, n, 2)]
prime = [2]
while True:
  p = a[0]
  if limit <= p:
    prime += a
    break
  prime.append(p)
  a = [j for j in a if j%p!=0]
  
pi = [0]*n
for i in range(len(prime)):
  ai = (prime[i]+1)//2
  if ai in prime:
    pi[prime[i]-1] = 1
    
s = [0]*n
s[0] = pi[0]
for i in range(len(pi)-1):
  s[i+1] = s[i] + pi[i+1]
s = [0,0] + s
for i in range(q):
  l, r = map(int, input().split())
  print(s[r+1]-s[l])

Submission status: Accepted

Solution code:
import numpy as np
L = 10**5


def main():
    is_prime = np.full(L+1, True, dtype=bool)
    is_prime[0:2] = False
    for i in range(2, int(np.sqrt(L))+1):
        if is_prime[i] == False:
            continue
        is_prime[i+i:L+1:i] = False
    # ここまで素数判定
    # ここから2017に似た数を判定
    is_like_2017 = np.full(L+1, False, dtype=bool)

    for i in range(2, L+1):
        if 2*i-1 > L:
            break
        if is_prime[i]:
            is_like_2017[2*i-1] = True

    is_like_2017[2] = False

    is_like_2017 = np.logical_and(is_prime, is_like_2017)
    accumulate = np.cumsum(is_like_2017)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
flag = [False]*100001
c = [0]*100002
n = int(input())

for i in range(2,100000):
    if(not(flag[i])):
        for j in range(i+i,100000,i):
            flag[j] = True

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

while(n):
    n-=1
    l,r = map(int,input().split())
    print(c[r]-c[l-1])

Submission status: Accepted

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

n = 10 ** 5
memo = [1] * (n+1)

for i in range(2, n):
  for j in range(2, n):
    if i * j > n:
      break
    memo[i*j] = 0
memo2 = memo[:]
memo2[1] = 0
for x in range(n+1):
  if x % 2 == 0 or memo[(x+1) // 2] == 0:
    memo2[x] = 0
  
c = [0]

for x in memo2[1:]:
  c.append(c[-1]+x)

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

Submission status: Accepted

Solution code:
Q = int(input())
l = []
r = []
for i in range(Q):
    a, b = map(int, input().split())
    l.append(a)
    r.append(b)
    
x =[True]*((10**5)+1)
x[0] = False
x[1] = False
s = [0, 0, 0]

for i in range(4, (10**5)+1, 2):
    x[i] = False

for j in range(3, (10**5)+1):
    if x[j] == False:
        s.append(s[-1])
        continue
    for k in range(2*j, (10**5)+1, j):
        x[k] = False
    if x[(j+1)//2] == True:
        s.append(s[-1]+1)
    else:
        s.append(s[-1])

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

Submission status: Accepted

Solution code:
Q=  int(input())
dp = [False]*(100001)
for i in range(2,100001):
    if not dp[i]:
        for j in range(2*i,100001,i):
            dp[j] = True
A = []
for i in range(3,100001):
    if not dp[i] and not dp[(i+1)//2]:
        A.append(i)
from bisect import bisect_left, bisect_right
queries = []
for _ in range(Q):
    l,r = map(int,input().split())
    queries.append([l,r])
for l,r in queries:
    idl = bisect_left(A,l)
    idr = bisect_right(A,r)
    print(idr-idl)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
q=int(input())
def primes(n):
    m=int(pow(n,0.5))
    is_prime=[True]*(n+1)
    is_prime[0]=False
    is_prime[1]=False
    for i in range(2,m+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]]
s=set(primes(10**5))
count=[0]*(10**5+1)
count[1]=0
count[2]=0
for i in range(3,10**5+1):
    if i in s and (i+1)//2 in s:
        count[i]=count[i-1]+1
    else:
        count[i]=count[i-1]
for i in range(q):
    l,r = map(int,input().split())
    print(count[r]-count[l-1])

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]]
dp=[0]*(10**5+1)
bp=[0]*(10**5+1)
for i in primes(10**5):
  dp[i]=1
for i in range(1,10**5+1):
  bp[i]+=bp[i-1]
  if i%2==0:
    continue
  if dp[(i+1)//2]==1 and dp[i]==1:
    bp[i]+=1
Q=int(input())
for _ in range(Q):
  l,r=map(int,input().split())
  print(bp[r]-bp[l-1])

Submission status: Accepted

Solution code:
INF=10**5+1
p=[1]*INF
for i in range(2,INF):
  if p[i]:
    for j in range(2*i,INF,i):p[j]=0
p[0],p[1]=0,0
dp=[0]*INF
for i in range(1,INF,2):
  if p[i]*p[(i+1)//2]:dp[i]=1
for i in range(1,INF):
  dp[i]+=dp[i-1]
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(dp[r+1]-dp[l-1])

Submission status: Accepted

Solution code:

q = int(input())
lr = []
for i in range(q):
    lr.append([int(j)-1 for j in input().split()])

import math
def test_div(index):
    if index < 2:
        return 0
    elif index == 2:
        return 1
    max = math.ceil(math.sqrt(index))+1
    ls = []
    for i in range(2,max):
        if index % i == 0:
            return 0
    return 1

primes = [2]

import time
st = time.time()
#[0] * 100000
ls = []
for i in range(100000):
    ls.append(test_div(i+1))
ls_like = [0] * 100000
for i in range(100000):
    if ls[i]:
        if ls[(i+2)//2-1]:
            ls_like[i] = 1
        else:
            ls_like[i] = 0
    else:
        ls_like[i] = 0

ls_acc = [0]
for i in range(100000):
    ls_acc.append(ls_acc[-1] + ls_like[i])

#print(time.time()-st)


for i in range(q):
    [l,r] = lr[i]
    print(ls_acc[r+1]-ls_acc[l])

Submission status: Accepted

Solution code:
def main():
    # エラトステネスのふるい
    MAX_NUM = 101010
    is_prime = [1 for _ in range(MAX_NUM)]
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, MAX_NUM):
        if not is_prime[i]:
            continue
        for j in range(i * 2, MAX_NUM, i):
            is_prime[j] = 0

    # 2017-like 数かどうか
    like2017 = [0 for _ in range(MAX_NUM)]
    for i in range(MAX_NUM):
        if i % 2 == 0:
            continue
        if is_prime[i] and is_prime[(i + 1) // 2]:
            like2017[i] = 1

    # 累積和
    cumsum = [0 for _ in range(MAX_NUM + 1)]
    for i in range(MAX_NUM):
        cumsum[i + 1] = cumsum[i] + like2017[i]

    Q = int(input())
    L = [None] * Q
    R = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        L[i] = l
        R[i] = r

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

def era(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

Q = i()
primes = []
l1 = era(100000)
for l in range(len(l1)):
    if l1[l] == 1:
        primes.append(l)
l2 = []
for l in primes:
    if (l+1)//2 in primes:
        l2.append(l)
for i in range(Q):
    l,r = I()
    print(bisect.bisect_right(l2,r)-bisect.bisect_left(l2,l))

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

judge = [0 for i in range(10**5+1)]
#素数リスト
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):    #nのルート+1
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)
for num in primes:
    judge[num] = 1
area = [0 for i in range(10**5+1)]
for num in primes[1:]:
    if judge[(num+1)//2] == 1:
        area[num] = 1
Area = [0]
for num in area:
    Area.append(Area[-1]+num)
def sumArea(l,r):
    return Area[r] - Area[l]
q = ir()
for i in range(q):
    l,r = lr()
    print(sumArea(l,r+1))

Submission status: Accepted

Solution code:
q = int(input())

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

def main(n):
    return 1 if is_prime(n) and is_prime((n + 1) // 2) else 0

MAX = 10 ** 5 + 100
A = [main(i) for i in range(MAX)]
# 累積和
acc = [0] * (MAX + 1)
for i in range(MAX):
    acc[i + 1] = acc[i] + A[i]

for i in range(q):
    l, r = map(int, input().split())
    # [l, r] なので r + 1 にする
    print(acc[r + 1] - acc[l])

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
is_prime = [1] * (10**5 + 1)
is_prime[0] = 0
is_prime[1] = 0
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] = 0
for i in range(10**5,1,-1):
    if is_prime[i]:
        if is_prime[(i+1)//2]:
            pass
        else:
            is_prime[i] = 0
is_prime = list(accumulate(is_prime))
for q in range(I()):
    l,r = readInts()
    l -= 1
    print(is_prime[r] - is_prime[l])

Submission status: Accepted

Solution code:
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, 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
    for i in range(len(is_prime)):
        if is_prime[i]: ass.append(i)
    return ass

d = primes(10**5)
d2017 = []
for i in d:
    if i > 10**5: break
    if (i+1)//2 in d:
        d2017.append(i)

import bisect
q = int(input())
ans = 0
for _ in range(q):
    l, r = map(int, input().split())
    index_l = bisect.bisect_left(d2017, l-1)
    index_r = bisect.bisect_right(d2017, r)
    print(index_r-index_l)

Submission status: Accepted

Solution code:
from itertools import accumulate
def prime(n):
  if n==1:
    return False
  else:
    for i in range(2,int(n**0.5)+1):
      if n%i==0:
        return False
    else:
      return True

l = [0 for i in range(10**6)] 

for i in range(1,10**5+1):
  if i%2==0:
    continue
  else:
    if prime(i):
      if prime((i+1)//2):
        l[i] = 1
l1 = list(accumulate(l))
q = int(input())
for i in range(q):
  l,r = map(int,input().split())
  print(l1[r]-l1[l-1])

Submission status: Accepted

Solution code:
Q=int(input())
l=[0]*100001
l2=[0]*100001
def d(n):
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
for i in d(100000):
   l[i]=1
for i in range(3,100001):
   if l[i] == 1:
      if l[(i+1)//2]==1:
         l2[i]=1
for i in range(1,100001):
   l2[i]+=l2[i-1]
qe=[list(map(int,input().split())) for i in range(Q)]
for i in qe:
   print(l2[i[1]]-l2[i[0]-1])

Submission status: Accepted

Solution code:
data = sorted(list(range(10**5+1)))
prime_bool = [True]*(10**5+1)
prime_bool[0] = False
prime_bool[1] = False
for i in range(2, len(data)):
  p = data[i]
  if prime_bool[p]:
    k = 2
    while k*p <= 10**5:
      prime_bool[k*p] = False
      k += 1

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

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

Submission status: Accepted

Solution code:
Q = int(input())
l, r = [], []
for i in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
max_r = max(r)

is_sosu = [1] * (max_r + 1)
is_sosu[0] = is_sosu[1] = 0
for i in range(2, max_r + 1):
    if is_sosu[i]:
        for j in range(i * i, max_r + 1, i):
            is_sosu[j] = 0

sums = [0] * (max_r + 1)
for i in range(1, max_r + 1):
    if is_sosu[i] and is_sosu[(i + 1) // 2]:
        sums[i] = sums[i - 1] + 1
    else:
        sums[i] = sums[i - 1]

for i in range(Q):
    print(sums[r[i]] - sums[l[i] - 1])

Submission status: Accepted

Solution code:
q=int(input())
l=[]
r=[]
for i in range(q):
    lr=list(map(int,input().split()))
    l.append(lr[0])
    r.append(lr[1])
n=sorted(r,reverse=True)[0]
prime=[True]*(n+1)
prime[0]=False
prime[1]=False
for i in range(2,int(n**(0.5))+1):
    if prime[i]:
        for j in range(i*2,n,i):
            prime[j]=False
a=[0]*(n+1)
for i in range(n+1):
    if i%2==0:
        continue
    if prime[i] and prime[(i+1)//2]:
        a[i]=1
s=[0]*(n+2)
for i in range(n+1):
    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:
#ABC 084 D - 2017 Like Number
from itertools import accumulate

def isPrime(x):
    if x == 2: flag = True
    else:
        flag = True
        if x % 2 == 0:
            flag = False
        
        i = 3
        while i**2 <= x and flag == True:
            if x % i == 0:
                flag = False
            else:
                i += 2
    return True if flag == True else False

q = int(input())
arr = []
max_v = 0
for i in range(q):
    l,r = map(int, input().split())
    arr.append((l,r))
    max_v = max(max_v, r)

res_arr = [0]*(max_v+1)
for i in range(3,max_v+1,2):
    v1, v2 = i, (i+1)//2
    if isPrime(v1) == True and isPrime(v2) == True:
        res_arr[i] = 1

cumsum = list(accumulate(res_arr))
#print(res_arr)
#print(cumsum)
for i in range(q):
    l,r = arr[i][0], arr[i][1]
    print(cumsum[r] - cumsum[l-1])

Submission status: Accepted

Solution code:
MAX = 10 ** 5
def sieve(n):
    f = [False] * (n + 1)
    res = []
    for i in range(2, n+1):
        if f[i]:
            continue
        res.append(i)
        for j in range(2 * i, n+1, i):
            f[j] = True
    return res

pn = sieve(MAX)
acc = [0] * (MAX + 1)
for p in pn:
    if p % 2 == 1 and (p + 1) // 2 in pn:
        acc[p] = 1
for i in range(2, MAX+1):
    acc[i] += acc[i-1]
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 prime_list(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())
LR = [list(map(int,input().split())) for _ in range(Q)]
p = prime_list(100010)
s = []
s.append(0)
for i in range(100001):
    if (i%2 == 1) and i in p and (i+1)//2 in p:
        s.append(s[i]+1)
    else:
        s.append(s[i])
for lr in LR:
    print(s[lr[1]+1]-s[lr[0]])

Submission status: Accepted

Solution code:
flag = [False]*100001
c = [0]*100002
n = int(input())

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

while(n):
    n-=1
    l,r = map(int,input().split())
    print(c[r]-c[l-1])