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 bisect

primes = [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]
q = int(input())
for i in range(q):
    L, R = map(int, input().split())
    print(len(primes[bisect.bisect_left(primes, L):bisect.bisect_right(primes, R)]))

Submission status: Accepted

Solution code:
N=10**5
A=[1 for i in range(N+1)]
for i in range(2,N+1):
    if A[i]==0:
        continue
    for j in range(i,N+1,i):
        if i==j:
            continue
        A[j]=0
P=set()
for i in range(2,N+1):
    if A[i]==1:
        P.add(i)
B=[0 for i in range(N+1)]
for i in range(3,N+1,2):
    if i in P and (i+1)//2 in P:
        B[i-1]=1
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=B[i]+S[i]
Q=int(input())
for line in range(Q):
    l,r=map(int,input().split())
    print(S[r]-S[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, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
a = primes(100000)
resemble = []
for i in range(len(a)):
    if a[i]:
        if a[(i+1)//2]:
            resemble.append(i)
n = int(input())
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
for i in range(n):
    l,r = map(int,input().split())
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print(q[i])

Submission status: Accepted

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

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
a = primes(100000)
resemble = []
for i in range(len(a)):
    if a[i]:
        if a[(i+1)//2]:
            resemble.append(i)
n = int(input())
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
#print(ans[:30])
for i in range(n):
    l,r = map(int,input().split())
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print(q[i])

Submission status: Accepted

Solution code:
likeprime = [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]

import sys
input = sys.stdin.readline

pp = [0] * 50001
for i in range(1,50001):
    if 2 * i - 1 in likeprime:
        pp[i] = pp[i -1] + 1
    else:
        pp[i] = pp[i -1]

Q = int(input())
for i in range(Q):
    l, r = (int(i) for i in input().split())
    print(pp[(r + 1)//2] - pp[(l + 1)//2 -1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from pprint import pprint
import math
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2:
        return []

    primes = [i for i in range(x)]
    primes[1] = 0  # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x):
            break
        if prime == 0:
            continue
        for non_prime in range(2 * prime, x, prime):
            primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes_list = set(primes(10**5+1))
list2017 = [i for i in primes_list if i%2 == 1 and (i+1)//2 in primes_list]
list2017.sort()

def search(n):
    s = 0
    e = len(list2017) - 1
    i = 0
    if n < list2017[s]:
        return 0
    if list2017[e] <= n:
        return len(list2017)
    while s < e:
        i = (s + e)//2
        if list2017[i] == n:
            return i+1
        elif list2017[i] < n:
            s = i
        else:
            e = i

        if s + 1 == e:
            return s + 1


for l,r in lr:
    # pprint([a for a in list2017 if l<=a<=r])
    lidx = search(l-1)
    ridx = search(r)
    # print(ridx)
    # print(lidx)
    print(ridx - lidx)

Submission status: Accepted

Solution code:
prime = [True] * 100001
cnt_list = [0] * 100002

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

for i in range(3, 100001, 2):
    if prime[i] and prime[(i+1)//2]:
        cnt_list[i] += 1

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

N = int(input())

for i in range(N):
    L, R = map(int,input().split())
    print(cnt_list[R] - cnt_list[L-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec  2 18:42:44 2018
ABC084D
@author: maezawa
"""

n = int(10**5)
is_prime = [True]*(n+1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, n//2):
    if is_prime[i] == True:
        for j in range(2*i,n+1,i):
            is_prime[j] = False

prime_numbers = set([i for i in range(n+1) if is_prime[i]])
similar = set([])

for i in prime_numbers:
    if (i+1) // 2 in prime_numbers:
        similar.add(i)
        
sim = [0]*(n+1)    
cnt = 0    
for i in range(n+1):
    if i in similar:
        cnt += 1
    sim[i]=cnt  

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

Submission status: Accepted

Solution code:
import math
import copy

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def realprimes(y):
    Y = primes(y)
    t = int((y + 1) / 2)
    bestprime = []

    for prime in Y:
        if prime != 2:
            prime2 = (prime + 1)//2
            pw = 0
            for i in range(2,int(math.sqrt(prime2)) + 2):
                if prime2 == 2:
                    break
                elif prime2 % i == 0:
                    pw = 1
                    break
            if pw == 0:
                bestprime.append(prime)

    T = bestprime
    V = set(Y) & set(T)
    return list(V)
W = realprimes(10**5 - 1)
W.sort()
W.append(10**5)
q = int(input())
s = []
for i in range(q):#h:高さ
    s.append([int(m) for m in input().split()])

j = 0
Z = []
for i in range(10 ** 5):
    if i < W[j]:
        Z.append(j)
    else:
        j += 1
        Z.append(j)

for i in range(q):
    if Z[s[i][0]] != Z[s[i][0] - 1]:
        print(Z[s[i][1]] - Z[s[i][0]] + 1)
    else:
        print(Z[s[i][1]] - Z[s[i][0]])

Submission status: Accepted

Solution code:
INF = 10**5+1
ac = [0 for i in range(INF)]
memo = [True for i in range(INF)]
for i in range(2,INF):
    if memo[i]:
        for j in range(2*i,INF,i):
            memo[j] = False

for x in range(3,INF,2):
    ac[x] = 1 if memo[x] and memo[(x+1)//2] else 0
for x in range(1,INF):
    ac[x] += ac[x-1]
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(ac[r]-ac[l-1])

Submission status: Accepted

Solution code:
import bisect

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

def prime_list(max_num):
    prime_list = [2]

    lens = 1
    n = 3
    while prime_list[-1] <= 10**5:
        if prime_num(n):
            prime_list.append(n)
            lens += 1
        n += 2

    count_list = [0 for i in range(max_num+1)]
    cnt = 0

    for n in range(3,max_num+1,2):

        tar1 = n
        tar2 = (n+1)//2

        ind2 = bisect.bisect_left(prime_list, tar2, 0, len(prime_list))
        if tar2 == prime_list[ind2]:

            ind1 = bisect.bisect_left(prime_list, tar1, 0, len(prime_list))
            if tar1 == prime_list[ind1]:
                cnt += 1

        count_list[n] = cnt
        count_list[n+1] = cnt

    return count_list

count_list = prime_list(10**5)
# print(count_list[91] - count_list[13-1])
# exit()

Q = int(input())

for i in range(Q):
    l,r = map(int, input().split())

    ans = count_list[r] - count_list[l - 1]
    print(ans)

Submission status: Accepted

Solution code:
NMAX = 10**5+1

is_prime = [True]*NMAX
for i in range(2, NMAX):
    if is_prime[i]:
        for j in range(2*i, NMAX, i):
            is_prime[j] = False

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

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

Submission status: Accepted

Solution code:
Num = [int(i) for i in range(2, 100001)]
Primes = [True for i in range(100001)]
Sim = [0 for i in range(100001)]

for i in range(2, 100001):
    if Primes[i] == True:
        j = i * 2
        while j < 100001:
            Primes[j] = False
            j += i

for i in range(3, 100001):
    if Primes[i] and Primes[(i+1)//2]:
        Sim[i] = Sim[i-1] + 1
    else:
        Sim[i] = Sim[i-1]

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

Submission status: Accepted

Solution code:
MAX_INT = int(1e5)


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
Q=int(input())
Numbers=[0]*100001
Primes=[]
Flag=0
Flag2=0
n=0
for i in range(2,50001):
  for p in Primes:
    if (2*i-1)%p==0:
      Flag=1
      break
    elif p>(2*i-1)**(1/2):
      break
  if Flag==0:
    Primes.append(2*i-1)
    for q in Primes:
      if i!=q and i!=2:
        if i%q==0 or i%2==0:
          Flag2=1
          break
      elif q>i**(1/2):
        break
    if Flag2==0:
      n+=1      
  Numbers[2*i-1]=n
  Numbers[2*i]=n
  Flag=0
  Flag2=0
for i in range(Q):
  l,r=map(int,input().split()) 
  print(Numbers[r]-Numbers[l-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
V = [1]*(10**5+1)
P = [0]*(10**5+1)
V[0] = 0
V[1] = 0
for i in range(10**5+1):
    if V[i] == 0:
        continue
    P[i] = 1
    for j in range(2,10**5):
        if i*j >= 10**5:
            break
        V[i*j] = 0
W = [0]*(10**5+1)
for i in range(10**5+1):
    if not V[i]:
        continue
    if V[(i+1)//2] == 1:
        W[i] = 1
accW = list( accumulate(W))
Q = int( input())
for i in range(Q):
    l, r = map( int, input().split())
    print(accW[r] - accW[l-1])

Submission status: Accepted

Solution code:
class imosOneDimension:
    def __init__(self, size):
        self.table = [0 for i in range(size)]

    def setTable(self):
        for i in range(len(self.table) - 1):
            if self.is_prime(i) and self.is_prime(int((i + 1) / 2)):
                self.table[i] = 1
                # self.table[i] += self.table[i - 1]

    def cumulativeSum(self):
        for i in range(1, len(self.table)):
            self.table[i] += self.table[i - 1]

    def is_prime(self, n):
        if n == 1:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


imos = imosOneDimension(size=10 ** 5 + 1)
imos.setTable()
imos.cumulativeSum()
q = int(input())
for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(imos.table[r] - imos.table[l - 1])

Submission status: Accepted

Solution code:
class imosOneDimension:
    def __init__(self, size):
        self.table = [0 for i in range(size)]

    def setTable(self):
        for i in range(len(self.table)-1):
            if is_prime(i) and is_prime(int((i + 1) / 2)):
                self.table[i] = 1
                # self.table[i] += self.table[i - 1]

    def cumulativeSum(self):
        for i in range(1, len(self.table)):
            self.table[i] += self.table[i - 1]


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

imos = imosOneDimension(size=10 ** 5 + 1)
imos.setTable()
imos.cumulativeSum()
q = int(input())
for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(imos.table[r] - imos.table[l - 1])

Submission status: Accepted

Solution code:
class imosOneDimension:
    def __init__(self, size):
        self.table = [0 for i in range(size)]

    def setTable(self):
        for i in range(len(self.table)-1):
            if is_prime(i) and is_prime(int((i + 1) / 2)):
                self.table[i] = 1
                # self.table[i] += self.table[i - 1]

    def cumulativeSum(self):
        for i in range(1, len(self.table)):
            self.table[i] += self.table[i - 1]


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

imos = imosOneDimension(size=10 ** 5 + 1)
imos.setTable()
tableOneHot = []
for i in range(len(imos.table)):
    if imos.table[i] == 1:
        tableOneHot.append(i)
#print(tableOneHot)
#print(imos.table)

imos.cumulativeSum()
#print(imos.table)
q = int(input())
for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(imos.table[r] - imos.table[l - 1])

Submission status: Accepted

Solution code:
def isprime(n):
    if(n==1):
        return False
    if(n==2):
        return True
    if(n%2==0):
        return False
    i=3
    while( i**2 <=n):
        if(n%i==0):
            return False
        i+=2
    return True


sosuu=[False]*(10**5+1)
for i in range(1,10**5+1):
    sosuu[i]=isprime(i)

like_2017=[0]*(10**5+1)
i=3
while(i<=10**5):
    if( sosuu[i] & sosuu[(i+1)//2]):
        like_2017[i]=1
    i+=2

ruiseki=[0]*(10**5 + 2)
for i in range(1,10**5+2):
    ruiseki[i]=ruiseki[i-1] + like_2017[i-1]

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

Submission status: Accepted

Solution code:
# Let N be max{r_i} = 10^5.
# time complexity: O(NlglgN + Q)
# space complexity: O(N)

import sys
fin = sys.stdin.readline


def sieve(n):
    is_prime = [True] * (n + 1)
    prime_numbers = []
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        if is_prime[i]:
            prime_numbers.append(i)
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return is_prime


Q = int(fin())
N = 10**5
queries = [[int(elem) for elem in fin().split()] for _ in range(Q)]
is_prime = sieve(N)
num_similar_prefix = [0] * (N + 1)
num_similar = 0
for i in range(1, N + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        num_similar += 1
    num_similar_prefix[i] = num_similar

for l, r in queries:
    if l == 0:
        num_similar = num_similar_prefix[r]
    else:
        num_similar = num_similar_prefix[r] - num_similar_prefix[l - 1]
    print(num_similar)

Submission status: Accepted

Solution code:
import bisect
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=[i for i in primes if (i+1)//2 in primes]
q=int(input())
for i in range(q):
    a,b=map(int, input().split())
    print(bisect.bisect_right(primes, b)-bisect.bisect_left(primes, a))

Submission status: Accepted

Solution code:
import math
import bisect


def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True


if __name__ == '__main__':
    q = int(input())
    array = [[int(x) for x in input().split()] for x in range(q)]
    nearby_2017 = [x for x in range(1, 100000, 2) if is_prime(x) and is_prime((x+1)/2)]
    for i, j in array:
        print(bisect.bisect_right(nearby_2017, j) - bisect.bisect_left(nearby_2017, i))

Submission status: Accepted

Solution code:
import numpy as np
a = np.arange(1, 100001)
t = np.ones([len(a)], dtype=bool)
for i in range(1, 50000):
    t[i + a[i]::a[i]] = False
t[0] = False
s = [0, 0]
for i in range(2, 100000):
    if i % 2:
        s.append(s[-1])
    else:
        if t[i] and t[(i + 2) // 2 - 1]:
            s.append(s[-1] + 1)
        else:
            s.append(s[-1])
Q = int(input())
ans = []
for i in range(Q):
    L, R = map(int, input().split())
    if L == 1:
        ans.append(s[R - 1])
    else:
        ans.append(s[R - 1] - s[L - 2])
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
import math
N = 10**5+1
numbers = [i for i in range(2,N+1)]
primes = []
x = numbers[0]
while x <= math.ceil(math.sqrt(N))+1:
    x = numbers[0]
    primes.append(x)
    numbers = [num for num in numbers if num%x != 0]
pset = set(primes) | set(numbers)
oddPrimes = [number for number in pset if (number+1)//2 in pset]
oddPrimes.sort()
#print(oddPrimes)
cumsum = [0 for _ in range(N+1)]
j=0
length = len(oddPrimes)
nextOP = oddPrimes[j]
for i in range(1,N+1):
    if i != nextOP:
        cumsum[i] = cumsum[i-1]
    else:
        cumsum[i] = cumsum[i-1] + 1
        if j+1 < length:
            j += 1
            nextOP = oddPrimes[j]
        else:
            nextOP = -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:
primes = [i for i in range(10**5+1)]
primes[1] = 0 

for p in primes:
    if p > int(10**(5/2)): break
    if p == 0: continue
    for non_prime in range(2 * p, 10**5+1, p): primes[non_prime] = 0

    prime = [prime for prime in primes if prime != 0]
prime2 = set([2*i-1 for i in prime])
like2017 = sorted(list(set(prime) & prime2))

def inpl(): return [int(i) for i in input().split()]


H = [0 for i in range(10**5+2)]
for i in like2017:
    H[i] = 1
for i in range(10**5+1):
    H[i+1] += H[i] 

Q = int(input())
ans = []
for i in range(Q):
    l, r = inpl() 
    ans.append(H[r]-H[l-1])
for i in ans:
    print(i)

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]


E = eratosthenes(10 ** 5 + 1)
P = [0] * (10 ** 5 + 1)
for e in E:
    P[e] = 1

like2017 = [0] * (10 ** 5 + 1)
for n in range(10 ** 5 + 1):
    if ((n + 1) / 2).is_integer():
        if P[n] and P[(n + 1) // 2]:
            like2017[n] = 1
like2017 = list(accumulate(like2017))

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

Submission status: Accepted

Solution code:
def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]

primes = eratosthenes(100000)
numbers = [(p+1)//2 for p in primes]
alike = list(set(primes)&set(numbers))
alike = [2*p-1 for p in alike]
alike.sort()
alike

cum = [0]*(10**5+1)
for p in alike:
    cum[p] = 1
import numpy as np
cum = np.array(cum)
cum = np.cumsum(cum)

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

Submission status: Accepted

Solution code:
import math


class LR:
    def __init__(self, l, r):
        self.left = l
        self.right = r


def is_prime(num):
    if (num < 2):
        return False
    elif(num == 2):
        return True
    elif (num % 2 == 0):
        return False
    sqrt_num = int(math.sqrt(num))
    for i in range(3, sqrt_num+1):
        if i % 2 == 0:
            continue
        if (num % i == 0):
            return False
    return True


def generate_prime_dict():
    prime_dict = {}
    for num in range(1, 100001):
        if is_prime(num):
            prime_dict[num] = 1
    return prime_dict


prime_dict = generate_prime_dict()

like_2017_dict = {}

cnt = 0
for n in range(100001):
    if n in prime_dict and ((n+1)/2) in prime_dict:
        cnt += 1
    like_2017_dict[n] = cnt


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

for lr in lrs:
    print(like_2017_dict[lr.right] - like_2017_dict[lr.left-1])