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: Time Limit Exceeded

Solution code:
Nl = [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())
R = []
for i in range(Q):
    R.append(list(map(int, input().split())))
for i in range(Q):
    tmp1 = 0
    tmp2 = 0
    for j in range(len(Nl)):
        if Nl[j - 1] < R[i][0] <= Nl[j]:
            tmp1 = j
        if Nl[j - 1] <= R[i][1] < Nl[j]:
            tmp2 = j
            break
    print(tmp2 - tmp1)

Submission status: Time Limit Exceeded

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 を出力せよ。
"""
q=int(input())
lr_ary = []
for _ in range(q):
  lr_ary.append(list(map(int, input().split())))

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

for l,r in lr_ary:
    ret=0
    for x in range(l,r+1,2):
        if prime[x] and prime[int((x+1)/2)]:
            ret += 1
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
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())
    ans = 0
    for a in range(l, r+1, 2):
        if a in p:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8
import random
Q = 0
L = []
R = []

# http://d.hatena.ne.jp/pashango_p/20090704/1246692091
def is_prime3(q,k=5):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in xrange(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

# 入力部分
Q = int(raw_input())
for i in range(Q):
  l, r = map(int, raw_input().split())
  L.append(l)
  R.append(r)

# 処理部分
for q in range(Q):
  cnt = 0
  for x in range(L[q], R[q]+1):
    if is_prime3(x) & is_prime3((x+1)/2):
      cnt += 1
  print cnt

Submission status: Time Limit Exceeded

Solution code:
def is_prime_trial_division(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
 

q = int(input())

plist = set()
#for i in range(1,100000,2):
#    if is_prime_trial_division(i):
#        if  int((i+1)/2) in plist or is_prime_trial_division(int((i+1)/2)):
#            plist.add(i)

plist=[79873, 3, 5, 45061, 90121, 13, 12301, 36877, 51217, 75793, 65557, 8221, 57373, 16417, 53281, 37, 36901, 38953, 51241, 22573, 18481, 36913, 20533, 63541, 88117, 41017, 47161, 61, 30781, 32833, 38977, 69697, 94273, 73, 6217, 4177, 34897, 55381, 2137, 10333, 22621, 14437, 82021, 43117, 49261, 57457, 88177, 94321, 10357, 18553, 61561, 8317,
12421, 30853, 75913, 28813, 65677, 71821, 12433, 53401, 84121, 157, 67741, 8353, 20641, 4261, 28837, 34981, 12457, 43177, 88237, 4273, 16573, 193, 6337, 43201, 67777, 26821, 88261, 18637, 24781, 55501, 80077, 26833, 63697, 10453, 6361, 61657, 6373, 82153, 94441, 96493, 49393, 61681, 69877, 16633, 28921, 47353, 12541, 14593, 26881, 4357, 41221, 96517, 12553, 24841, 49417, 8461, 33037, 16657, 277, 61717, 45337, 51481, 2341, 63781, 80173, 39217, 313, 12601, 43321, 51517, 41281, 8521, 26953, 78157, 55633, 86353, 82261, 4441, 65881, 84313, 67933, 74077, 80221, 18793, 31081, 94573, 78193, 20857, 45433, 72073, 397, 86413, 92557, 14737, 37273, 67993, 47521, 421, 61861, 2473, 45481, 63913, 29101, 47533, 12721, 98737, 51637, 59833, 49597, 27073, 88513, 41413, 78277, 457, 25033, 37321, 39373, 4561, 22993, 12757, 8677, 14821, 39397, 70117, 6637, 37357, 45553, 35317, 2557, 57853, 6661, 31237, 8713, 21001, 4621, 23053, 49681, 68113, 33301, 16921, 541, 55837, 2593, 70177, 47653, 12841, 45613, 76333, 12853, 43573, 94777, 25153, 21061, 43597, 74317, 10837, 31321, 80473, 92761, 47713, 613, 31333, 10861, 43633, 55921, 27253, 94837, 47737, 6781, 31357, 55933, 82561, 23173, 74377, 98953, 17041, 41617, 661, 25237, 92821, 64153, 70297, 17053, 53917, 673, 15013, 88741, 33457, 17077, 47797, 62137, 68281, 8893, 35521, 84673, 37573, 43717, 21193, 27337, 10957, 96973, 33493, 84697, 733, 92893, 15073, 27361, 2797, 64237, 47857, 757, 31477, 56053, 66301, 92941, 15121, 45841, 76561, 94993, 21277, 29473, 72481, 13093, 19237, 49957, 56101, 2857, 58153, 56113, 9013, 39733, 76597, 60217, 66361, 84793, 97081, 80701, 21313,
27457, 88897, 4933, 80713, 6997, 31573, 37717, 52057, 35677, 2917, 70501, 11113, 17257, 54121, 877, 52081, 54133, 64381, 56197, 15241, 17293, 7057, 11161, 97177, 88993, 41893, 54181, 72613, 68521, 93097, 9133, 15277, 60337, 84913, 46021, 29641, 54217, 91081, 93133, 99277, 76753, 5077, 60373, 25561, 74713, 9181, 33757, 70621, 17377, 997, 5101, 19441, 3061, 5113, 48121, 15361, 64513, 23557, 62473, 15373, 52237, 19477, 44053, 80917, 9241, 95257, 78877, 62497, 82981, 66601, 7213, 50221, 58417, 11317, 78901, 25657, 9277, 46141, 48193, 1093, 13381, 44101, 37957, 21577, 58441, 62533, 42061, 56401, 95317, 52321, 13417, 5233, 56437, 81013, 23677, 1153, 31873, 68737, 83077, 35977,
66697, 87181, 3217, 54421, 21661, 40093, 50341, 21673, 33961, 58537, 95401, 1201, 3253, 46261, 1213, 44221, 62653, 72901, 50377, 58573, 64717, 89293, 48337, 1237, 87253,
23773, 60637, 97501, 7393, 44257, 52453, 11497, 72937, 31981, 3313, 40177, 54517, 91381, 7417, 99577, 36097, 91393, 19717, 44293, 75013, 34057, 70921, 54541, 40213, 52501, 83221, 97561, 81181, 83233, 5413, 66853, 1321, 87337, 85297, 7477, 62773, 93493, 21817, 5437, 60733, 58693, 70981, 25933, 99661, 77137, 85333, 19801, 27997, 95581, 42337, 1381, 19813, 23917, 7537, 13681, 15733, 91513, 56701, 75133, 87421, 9601, 95617, 42373, 38281, 69001, 87433, 36241, 54673, 19861, 28057, 11677, 66973, 26017, 34213, 1453, 32173, 75181, 11701, 73141, 3517, 9661, 54721, 56773, 93637, 5581, 85453, 69073,
17881, 87517, 34273, 95713, 30181, 79333, 83437, 67057, 97777, 56821, 9721, 95737, 79357, 87553, 60937, 97813, 56857, 15901, 24097, 30241, 48673, 99877, 38461, 56893, 71233, 5701, 7753, 22093, 34381, 52813, 36433, 67153, 1621, 9817, 18013, 13921, 36457, 13933, 81517, 48757, 1657, 32377, 52861, 61057, 50821, 28297, 48781, 3733, 65173, 16033, 83617, 9901, 59053, 71341, 18097, 79537, 26293, 71353, 54973, 67273, 73417, 26317, 50893, 34513, 18133, 85717, 1753, 93913, 52957, 61153, 98017, 81637, 28393, 89833, 32497, 57073, 9973, 40693, 83701, 7933, 18181, 73477, 57097, 46861, 65293, 55057, 32533, 12073, 18217, 42793, 79657, 30517, 91957, 59197, 83773, 89917, 26437, 77641, 18253, 61261, 79693, 1873, 63313, 69457, 94033, 53077, 59221, 30553, 73561, 44893, 96097,
24421, 57193, 40813, 30577, 61297, 8053, 69493, 53113, 12157, 18301, 20353, 26497, 65413, 18313, 49033, 92041, 1933, 46993, 59281, 6037, 67477, 57241, 65437, 96157, 24481, 8101, 63397, 87973, 94117, 47017, 71593, 30637, 85933, 38833, 4021, 96181, 6073, 36793, 79801, 81853, 30661, 1993, 75721, 16333, 59341, 12241, 42961, 67537, 51157, 4057, 65497, 18397, 73693, 2017, 22501, 6121, 30697, 6133, 16381]

#print(plist)


for i in range(q):
    tl, tr = map(int,input().split(' '))
    cnt=0
    subs = set()
    for j in range(tl,tr+1,2):
#        subs.add(j)
#    cnt = len(plist.intersection(subs))
#    print(cnt)
        if j in plist:
            cnt +=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def getNearestValue(list, num):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    if list[idx] < num:
    	return idx + 1
    else:
    	return idx

ans = [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]
ans_num = []
Q = int(input())
for i in range(Q):
	l,r = map(int,input().split(" "))
	l_i = getNearestValue(ans,l)
	r_i = getNearestValue(ans,r)

	if l_i == r_i:
		if ((l in ans) or (r in ans)):
			r_i += 1

	ans_num.append(r_i - l_i)


for i in range(Q):
	print(ans_num[i])

Submission status: Time Limit Exceeded

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

import sys
import random

import functools


@functools.lru_cache(1000000)
def is_prime3(q, k=5):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True


q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    ans = 0
    for i in range(l, r + 1, 2):
        if is_prime3(i) and is_prime3((i + 1) // 2):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8
import random
Q = 0
L = []
R = []

# http://d.hatena.ne.jp/pashango_p/20090704/1246692091
def is_prime3(q,k=10):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in xrange(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

# 入力部分
Q = int(raw_input())
for i in range(Q):
  l, r = map(int, raw_input().split())
  L.append(l)
  R.append(r)

# 処理部分
for q in range(Q):
  cnt = 0
  for x in range(L[q], R[q]+1):
    if is_prime3(x) & is_prime3((x+1)/2):
      cnt += 1
  print cnt

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8
import random
Q = 0
L = []
R = []

# http://d.hatena.ne.jp/pashango_p/20090704/1246692091
def is_prime3(q,k=40):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in xrange(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

# 入力部分
Q = int(raw_input())
for i in range(Q):
  l, r = map(int, raw_input().split())
  L.append(l)
  R.append(r)

# 処理部分
for q in range(Q):
  cnt = 0
  for x in range(L[q], R[q]+1):
    if is_prime3(x) & is_prime3((x+1)/2):
      cnt += 1
  print cnt

Submission status: Time Limit Exceeded

Solution code:
import math


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

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

        if serial >= sqrt:
            return input_list

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

q = input()
lr = []
max_num = 0
input_list = sieve_of_erastosthenes(100000)
prime_list = [i for i, b in enumerate(input_list) if b == True]
for ii in xrange(q):
    tmp = map(int, raw_input().split(" "))
    count = 0
    # max_num = max(max(tmp), max_num)
    # lr.append(tmp)
    for j in xrange(tmp[0], tmp[1] + 1):
        if j in prime_list and (j + 1) / 2 in prime_list:
            count += 1

    print count

Submission status: Time Limit Exceeded

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

import sys
import random

import functools


@functools.lru_cache(1000000)
def is_prime3(q, k=50):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True


q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    ans = 0
    for i in range(l, r + 1, 2):
        if is_prime3(i) and is_prime3((i + 1) // 2):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8                                                                                         
import random

def is_prime(q,k=10):
    #計算するまでもなく判定できるものははじく                                                         
    if q < 2: return False # 2未満に素数はない                                                        
    if q == 2 or q == 3 or q == 5: return True # 2,3,5は素数                                          
    if q % 2 == 0 or q % 3 == 0 or q % 5 == 0: return False # 2,3,5の倍数は合成数                     

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める                                                  
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    #判定をk回繰り返す                                                                                
    for i in xrange(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック                                                                
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True


Q = int(raw_input())
LR = []
for i in range(Q):
    l, r = map(int, raw_input().split())
    LR.append((l, r))

for l, r in LR:
    count = 0
    for j in range(l, r+1, 2):
        if is_prime(j):
            if is_prime((j+1)/2):
                count += 1
    print count