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,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

    def sowa(self, n):
        r = 1
        for k,v in self.division(n):
            t = 1
            for i in range(1,v+1):
                t += math.pow(k, i)
            r *= t
        return r

def main():
    q = I()
    a = [LI() for _ in range(q)]
    pr = Prime(10**10)
    b = [0]
    for i in range(1,10**5+1):
        if i%2==1 and pr.is_prime(i) and pr.is_prime((i+1)//2):
            b.append(b[-1] + 1)
        else:
            b.append(b[-1])
    r = []
    for c,d in a:
        r.append(b[d]-b[c-1])

    return '\n'.join(map(str,r))

print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/python

import math
import sys

def is_prime(n):
    if n == 1:
        return False

    for i in xrange(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def main(argv):
    primes = [False]
    for i in xrange(1, 100000 + 1):
        primes.append(is_prime(i))

    counter = 0
    results = [0]
    for i in xrange(1, 100000 + 1):
        if i % 2 == 0:
            results.append(counter)
            continue

        if primes[i] and primes[(i + 1) / 2]:
            counter += 1
        results.append(counter)

    line = sys.stdin.readline()
    while line:
        Q = int(line.rstrip("\n"))
        for i in xrange(Q):
            l, r = map(
              lambda i: int(i), sys.stdin.readline().rstrip("\n").split(" "))

            print results[r] - results[l - 1]

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Accepted

Solution code:
prime = {1:False}
for i in range(2,100001):
    if i not in prime:
        prime[i] = True
        for j in range(i*2,100001,i):
            prime[j] = False

like = {0:0}
for i in range(1,100001):
    like[i] = like[i-1] + int((i%2==1) and prime[i] and prime[int((i+1)/2)])

Q = int(input())
for i in range(Q):
    LR = list(map(int,input().split()))
    print("%d"%(like[LR[1]]-like[LR[0]-1]))

Submission status: Accepted

Solution code:
Q = int(raw_input())
query = [map(int, raw_input().split(' ')) for _ in range(Q)]

composite_number = [False] * (100001)
for i in range(2, 100001):
    if not composite_number[i]:
        for j in range(i+i, 100001, i):
            composite_number[j] = True
    
similar_number = [0] * 100001
for i in range(3, 100001, 2):
    if not composite_number[i] and not composite_number[(i+1)/2]:
        similar_number[i] += 1

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

for l, r in query:
    print similar_number[r] - similar_number[l-1]

Submission status: Accepted

Solution code:
from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
ruiseki=0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        ruiseki+=1
    prime2017[x] = ruiseki
q=int(input())
lr_ary = []
for _ in range(q):
    l,r=list(map(int, input().split()))
    print(prime2017[r]-prime2017[l-1])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
q = int(input())
p = [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]

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

    a = bisect_left(p,l)
    b = bisect_right(p,r)
    print(b-a)

Submission status: Accepted

Solution code:
Q = int(input())
point=[]
query=[]
for i in range(Q):
    l,r=[int(i) for i in input().split()]
    point.append(l)
    point.append(r)
    query.append([l,r])
# print(point)
point_uniq = list(set(point))
# print(point_uniq)
point_sorted = sorted(point_uniq)
# print(point_sorted)

def binary_search(list,target):

	result = -1
	left = 0
	right = len(list) - 1

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

	return result


#ふるい
SIZE=100001
is_prime=[True for i in range(SIZE)]
is_prime[0]=False
is_prime[1]=False
for i in range(2,SIZE):
    # print(i,is_prime)
    if is_prime[i]==False:
        continue
    else:
        tmp=i+i
        while(tmp<SIZE):
            is_prime[tmp]=False
            tmp+=i

MIN=point_sorted[0]
MAX=point_sorted[-1]
N_count=0
index=1
range_N=[]
for i in range(MIN,MAX+1):
    if i%2==0:
        continue
    if is_prime[i]==True and is_prime[int((i+1)/2)]==True:
        N_count+=1
    if i==point_sorted[index]:
        index+=1
        range_N.append([MIN,i,N_count])
# print(range_N)

for q in query:
    ans=0
    l_index=binary_search(point_sorted,q[0])
    r_index=binary_search(point_sorted,q[1])

    # l_index=point_sorted.index(q[0])
    # r_index=point_sorted.index(q[1])
    # print(q,l_index,r_index)
    if l_index==r_index:
        ans=1 if is_prime[q[0]] and is_prime[int((q[0]+1)/2)] else 0
    elif l_index==0:
        ans=range_N[r_index-1][2]
    else:
        ans=range_N[r_index-1][2]-range_N[l_index-1][2]
        if is_prime[q[0]] and is_prime[int((q[0]+1)/2)]:
            ans+=1
    print(ans)

Submission status: Accepted

Solution code:
import math
from functools import lru_cache

n=int(input())
@lru_cache()
def sosu(l):
  if l ==2:
    return 1
  elif l % 2==0 or l==1 or l==3/2 or l==0:
    return 0
  else:
    for d in range(3, math.floor(math.sqrt(l))+1,2):
      if l % d == 0:
        return 0
        break
    else:
      return 1

m=0
li=[]
for j in range(0,100001):
  m+=sosu(j)*sosu((j+1)/2)
  li.append(m)

for i in range(n):
  a,b=[int(i) for i in input().split()]
  print(li[b]-li[a-1])

Submission status: Accepted

Solution code:
import bisect

def main():
    Q = int(input())
    LR = tuple(tuple(map(int, input().split())) for _ in [0] * Q)

    l = min(LR)[0]
    r = max(LR, key=lambda x: x[1])[1]
    num = []
    apnd = num.append
    for i in range(l, r + 1, 2):
        x = (i + 1) // 2
        if is_prime(i) and is_prime(x):
            apnd(i)

    for l, r in LR:
        x = bisect.bisect_left(num, l)
        y = bisect.bisect_right(num, r)
        print(y - x)

def is_prime(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True

main()

Submission status: Accepted

Solution code:
Q = int(input())

M = 10**5+5
primes = [True] * M
primes[0] = False
primes[1] = False


for i in range(2, M):
    if primes[i]:
        for j in range(2, (M-1)//i+1):
            primes[i*j] = False

# print(primes)                                                                    
cnt = [0] * M

for i in range(3, M):
    cnt[i] = cnt[i-1]
    if primes[i] and primes[(i+1)//2]:
        cnt[i] += 1
# print(cnt)                                                                       
queues = []
for q in range(Q):
    l, r = map(int, input().split())
    queues.append((l, r))

for l, r in queues:
    print(cnt[r] - cnt[l-1])

Submission status: Accepted

Solution code:
SIZE = int(1e5 + 1)
is_prime = [True] * SIZE
is_prime[0] = is_prime[1] = False
for i in range(2, SIZE):
    if is_prime[i]:
        for j in range(i * 2, SIZE, i):
            is_prime[j] = False

cnt = [0] * (SIZE)
for i in range(1, SIZE, 2):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        cnt[i] += 1

for i in range(1, SIZE):
    cnt[i] += 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:
MAXN = 100001
isPrime = [True for x in range(0, MAXN)]

def findPrime():
    isPrime[1] = False
    for i in range(2, MAXN):
        if isPrime[i]:
            for j in range(i + i, MAXN, i):
                isPrime[j] = False

findPrime()

cache = [0 for x in range(0, MAXN)]

pSum = 0
for i in range(1, MAXN, 2):
    cache[i] = pSum
    if isPrime[i] and isPrime[(i+1)//2]:
        cache[i] += 1
    pSum = cache[i]

Q = int(input())

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

Submission status: Accepted

Solution code:
Q = int(input())

n = 10 ** 5
is_prime = [True for i in range(n)]
is_prime[0], is_prime[1] = False, False
for i in range(2, n):
    if is_prime[i]:
        j = 2 * i
        while j < n:
            is_prime[j] = False
            j += i

like_num = [0 for i in range(n)]
rec = 0
for i in range(1, n, 2):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        rec += 1
    like_num[i] = rec

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

Submission status: Accepted

Solution code:
import math
def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    for i in xrange(3, int(math.sqrt(n))+1, 2):
        if n%i == 0:
            return False
    return True

m = list()
s = 0
for i in xrange(10**5):
    if is_prime(i) and is_prime((i+1)/2):
        s += 1
    m.append(s)

n = input()
for _ in xrange(n):
    s = 0
    a, b = map(int, raw_input().split())
    print m[b] - m[a-1]

Submission status: Accepted

Solution code:
MAX_X = 100000

a = [True] * MAX_X
a[0] = a[1] = False

for (i, isprime) in enumerate(a):
    if isprime:
        for n in range(i*i, MAX_X, i):
            a[n] = False

pre = [0, 0]

for i in range(3, MAX_X + 1, 2):
    if a[i] and a[(i + 1) // 2]:
        pre.append(pre[-1] + 1)
    else:
        pre.append(pre[-1])

q = int(input())

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import bisect
p=[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=input()
while True:
    try:
        l,r=map(int,input().split())
        l_index=bisect.bisect_left(p,l)
        r_index=bisect.bisect_right(p,r)
        print(len(p[l_index:r_index]))
    except:
        break;

Submission status: Accepted

Solution code:
q = int(input())
from math import sqrt
l = list(range(2,100000))
msqrt = int(sqrt(100000))
first = l[0]
prime = []
like = []
import bisect as bs
while first < msqrt:
    prime.append(first)
    l = list(filter(lambda x: x%first != 0, l))
    h = (first+1)//2
    ix = bs.bisect_left(prime, h)
    if prime[ix] == h:
        like.append(first)
    first = l[0]
prime.extend(l)
for ll in l:
    h = (ll+1)//2
    ix = bs.bisect_left(prime, h)
    if prime[ix] == h:
        like.append(ll)
for i in range(q):
    l, r = (int(x) for x in input().split())
    print(bs.bisect_right(like, r)-bs.bisect_left(like, l))

Submission status: Accepted

Solution code:
is_p = []
pre = []

N = 100003

for i in range(N):
    is_p.append(1)
    pre.append(0)

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

for i in range(1,N) :
    if i % 2 == 1 :
        if is_p[i] and is_p[ (i+1)//2 ] :
            pre[i] = 1
    pre[i] = pre[i-1] + pre[i]

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

Submission status: Accepted

Solution code:
import bisect


def eratosthenes_generator():
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            m += 2 * b
            while m in h:
                m += 2 * b
            h[m] = b
            del h[n]
        else:
            m += 2 * n
            while m in h:
                m += 2 * n
            h[m] = n
            yield n
        # print(n, h)
        n += 2


ps = {2}
like2017s = [3]
for p in eratosthenes_generator():
    if p % 4 == 1 and (p + 1) // 2 in ps:
        like2017s.append(p)
    ps.add(p)
    if p >= 1e5:
        break
# print(like2017s)

q = int(input())
buf = []
for l, r in (map(int, input().split()) for _ in range(q)):
    li = bisect.bisect_left(like2017s, l)
    ri = bisect.bisect(like2017s, r)
    # if like2017s[li] == l:
    #     li -= 1
    buf.append(ri - li)
    # print(li, ri)
print('\n'.join(map(str, buf)))

Submission status: Accepted

Solution code:
from bisect import *
a = [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]
n = int(input())
for l in range(n):
    k, m = list(map(int, input().split()))
    print(bisect_right(a, m) - bisect_left(a, k))

Submission status: Accepted

Solution code:
p = [True] * 100020
for x in xrange(2, int(100020 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100020):
            if y * x >= 100020:
                break
            p[x * y] = False
p[0], p[1] = False, False
e, s = [], 0
for i in xrange(100020):
    e.append(s)
    if p[i] and p[(i + 1) / 2]:
        s += 1
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print e[r + 1] - e[l]

Submission status: Accepted

Solution code:
import numpy as np
n=123456
q = int(input())

is_prime = np.ones(n+1,dtype=int)
is_prime[0]=0
is_prime[1]=0

for i in range(2,n+1):
    if(is_prime[i]==1):
        j=i+i
        while j <= n:
            is_prime[j] = 0
            j += i

cnt = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,n+1)]

for i in range(1,n+1):
    cnt[i]+=cnt[i-1]

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

Submission status: Accepted

Solution code:
def isprime(x):
  if x < 2: return False
  for d in range(2, int(x**0.5)+1):
    if x % d == 0: return False
  return True

isp = list(map(isprime, range(100001)))
w = [0]*100001
for i in range(100001):
  if i > 2 and isp[i] and isp[(i + 1)//2]:
    w[i] = 1

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

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

Submission status: Accepted

Solution code:
prime = [True]*(10**5+1)
prime[0] = False
prime[1] = False

for a in range(2,318): # >>> gmpy2.isqrt(10**5+1) -> mpz(316)
  if prime[a] == False:
    continue
  else:
    for b in range(a*2,10**5+1,a): 
      prime[b] = False
"""
print prime
import gmpy2

for a in range(0,10**5+1):
  if prime[a] != gmpy2.is_prime(a):
    print "NO"
    print a
"""
ans = [0]*(10**5+1)
now = 0
for a in range(3,10**5+1,2):
  if prime[a] == True and prime[(a+1)/2] == True:
    now = now + 1
  ans[a] = now

q = int(raw_input())
for a in range(q):
  l,r = map(int,raw_input().split(" "))
  x = ans[r] - ans[l]
  if prime[l] == True and prime[(l+1)/2] == True:
    x = x + 1
  print x