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: Runtime Error

Solution code:
from itertools import accumulate, count, islice, takewhile
 
def eratosthenes():
    d = {}
    for q in count(2):
        p = d.pop(q, None)
        if p:
            x = next(x for x in count(q + p, p) if x not in d)
            d[x] = p
        else:
            yield q
            d[q*q] = q

def likes():
    xs = set()
    for p in eratosthenes():
        if p in xs:
            yield p
        xs.add(2*p - 1)

likeset = set(takewhile(lambda n: n <= 100000, likes()))
onehot = (i in likeset for i in range(100000))
likecounts = list(accumulate(onehot))

q = int(input())
lrs = [[int(x) for x in input().split()] for _ in range(q)]

for l, r in lrs:
    print(likecounts[r+1] - likecounts[l-1])

Submission status: Runtime Error

Solution code:
import bisect


def primes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * (int((n - i * i - 1) / (2 * i)) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


q = int(input())
array = [[int(x) for x in input().split()] for z in range(q)]

primes_array = primes(10000+1)
res_primes = [0 for x in range(10000+1)]
cum_sum = 0
for x in range(10000+1):
    if x in primes_array and (x+1) // 2 in primes_array:
        cum_sum += 1
    res_primes[x] = cum_sum

for l, r in array:
    res = res_primes[r] - res_primes[l-1]
    print(res)

Submission status: Runtime Error

Solution code:
import bisect


def primes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * (int((n - i * i - 1) / (2 * i)) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


q = int(input())
array = [[int(x) for x in input().split()] for z in range(q)]

primes_array = primes(10000)
res_primes = [0 for x in range(10000+1)]
cum_sum = 0
for x in range(10000+1):
    if x in primes_array and (x+1) // 2 in primes_array:
        cum_sum += 1
    res_primes[x] = cum_sum

for l, r in array:
    res = res_primes[r] - res_primes[l-1]
    print(res)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
x,y = (n+m-2) , min((n-1),(m-1))
ans = 1
i, j = x, 1
while(i != x-y or j != y+1):
  if ans % j:
    ans *= i
   # print(i)
    i -= 1
  else:
    ans //= j
    #print(j)
    j += 1
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
isPrime = [True for i in range(10001)]
isPrime[1] = False
isPrime[0] = False

for i in range(2, 10001):
    if isPrime[i]:
        j = 2
        while i*j <= 10000:
            isPrime[i*j] = False
            j += 1

q = int(input())
qu = list()
for i in range(q):
    qu.append(list(map(int, input().split())))

for a in qu:
    ans = 0
    for i in range(a[0], a[1]+1):
        if isPrime[i]:
            if isPrime[(i+1)//2]:
                ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
N=int(input().strip())
primes=sorted(eratosthenes(int(1e5)))
p_set=set(primes)
primes2=[]
for p in primes:#MlogM
    if (p+1)//2 in p_set:
        primes2.append(p)
for i in range(N):#N
    l,r=map(int,input().split())
    li=binsearch_lb(primes2,l)#l以上のインデックス logM
    ri=binsearch_ub(primes2,r)#r以下のインデックス
    print(ri-li+1)

Submission status: Runtime Error

Solution code:
import gmpy2

n=int(input())
s=[[0] for i in range(100000)]

Submission status: Runtime Error

Solution code:
work = [True] * 100001
work[0] = False
work[1] = False
primes = []
for i in range(100001):
    if work[i]:
        primes.append(i)
        for j in range(2, 100001 // i):
            work[j * i] = False

ret = [i for i in primes if (i + 1) // 2 in primes]

csum = [0]
index = 0
for i in range(1, 10001):
    if i < ret[index]:
        csum.append(csum[-1])
    else:
        csum.append(csum[-1] + 1)
        index += 1

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

Submission status: Runtime Error

Solution code:
n = int(input())
lr = [None]*100000
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=0
        

for j in range(2,int(math.rmax**0.5+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[int((i+1)/2)] == 0:
        p[i] = 0
p[2] = 0
for i in range(2,rmax):
    p[i+1] += p[i]  

for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])

Submission status: Runtime Error

Solution code:
import math
n = int(input())
lr = [None]*10000
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=0
        

for j in range(2,int(math.sqrt(rmax)+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[int((i+1)/2)] == 0:
        p[i] = 0
p[2] = 0
for i in range(2,rmax):
    p[i+1] += p[i]  

for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])

Submission status: Runtime Error

Solution code:
import math
n = int(input())
lr = [None]*10000
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=0
        

for j in range(2,int(math.sqrt(rmax)+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[(i+1)//2] == 0:
        p[i] = 0
p[2] = 0
for i in range(2,rmax):
    p[i+1] += p[i]  

for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])

Submission status: Runtime Error

Solution code:
import math
n = int(input())
lr = [None]*10000
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=0
        

for j in range(2,int(math.sqrt(rmax)+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[(i+1)//2] == 0 and p[i] == 1:
        p[i] = 0
p[2] = 0
for i in range(2,rmax):
    p[i+1] += p[i]  

for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])

Submission status: Runtime Error

Solution code:
import math
n = int(input())
lr = [None]*10000
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=0
        

for j in range(2,int(math.sqrt(rmax)+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[(i+1)//2] == 0:
        p[i] = 0
for i in range(2,rmax):
    p[i+1] += p[i]  

for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])

Submission status: Runtime Error

Solution code:
import math
n = int(input())
lr = [None]*10000
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=1
        

for j in range(2,int(math.sqrt(rmax)+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[(i+1)//2] == 0:
        p[i] = 0
for i in range(1,rmax):
    p[i+1] +=p[i]
  


for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])
    
for i in range(rmax):
    print(i, p[i])

Submission status: Runtime Error

Solution code:
import math
n = int(input())
lr = [None]*10000
BT = False
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=0
        

for j in range(2,int(math.sqrt(rmax)+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[(i+1)//2] == 0:
        p[i] = 0
for i in range(2,rmax):
    p[i+1] +=p[i]
  

for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])

Submission status: Runtime Error

Solution code:

import itertools
import pandas as pd
import math 
from collections import defaultdict as dd
import numpy as np
import pandas as pd
import math

def check_num(target):
    check_count = 0
    divines = [i for i in range(1, target+1)]

    for i in divines:
        if int(target%i) == 0:
            check_count += 1

        if check_count >= 3:
            break

    if check_count == 2:
        return 1

    else:
        return 0


def main():
    N = int(input())

    for n in range(N):
        l, r = map(int,input().split())
        target_nums = []
        for i in range(l, r+1):
            if i%2 == 1:
                target_nums.append(i)

        count = 0
        for target_num in target_nums:
            if target_num == 1:
                continue

            check_2017 = 0
            check_2017 += check_num(target_num)

            check_2017 += check_num(int((target_num+1)/2))
            if check_2017 == 2:
                count += 1
        print (count)


if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache
from math import sqrt


@lru_cache()
def check(num):
    for i in range(2, int(sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True


@lru_cache()
def pos(num):
    if num == 1:
        return 0
    return pos(num - 1) + (1 if check(num) and check((num + 1) // 2) else 0)


def main():
    T = int(input())
    for _ in range(T):
        l, r = map(int, input().split())
        print(pos(r) - pos(l - 1))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

def isPrime(num):
    if num < 2:
        return False
    else:
        rootNum = math.floor(math.sqrt(num))
        for i in range(2,rootNum+1):
            if num % i == 0:
                return False
    return True

def solve():
    lst = []
    count = int(input())
    for i in range(count):
        ans = 0
        l, r = map(int, input().split())
        t = l
        while k <= r
            if isPrime(k) and isPrime((k+1)/2):
                ans += 1
            k += 2
        lst.append(str(ans))
    print('\n'.join(lst))
solve()

Submission status: Runtime Error

Solution code:
f = [False for i in range(100001)]
c = [0 for i in range(100001)]

for i in xrange(2, 100001):
    if not f[i]:
        for j in range(2*i, 100001, i):
            f[j] = True
for i in xrange(3, 100001, 2):
    if not f[i] and not f[int((i+1)/2)]:
        c[i] += 1
for i in xrange(3, 100001):
    c[i] += c[i-1]
    
n = int(input())
while n:
    l, r = list(map(int, input().split()))
    print (c[r]-c[l-1])
    n -= 1

Submission status: Runtime Error

Solution code:
Q = int(input())
isPrime = [-1 for x in range(10001)]
isPrime[1],isPrime[2] = False,True
for i in range(Q):
    ans = 0
    l,r = map(int,input().split())
    for c in range(l,r+1,2):
        other = (c+1)//2
        if isPrime[c] == -1:
            for j in range(2,int(c**0.5)+1):
                if c % j == 0:
                    isPrime[c] = False
                    break
            else:
                isPrime[c] = True
        if isPrime[other] == -1:
            for j in range(2,int(other**0.5)+1):
                if other % j == 0:
                    isPrime[other] = False
                    break
            else:
                isPrime[other] = True
                
        if isPrime[c] and isPrime[other]:
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
Q = int(input())
isPrime = [-1 for x in range(10001)]
isPrime[1],isPrime[2] = False,True
for i in range(Q):
    ans = 0
    l,r = map(int,input().split())
    for c in range(l,r+1,2):
        other = (c+1)//2
        if isPrime[c] == -1:
            for j in range(2,int(c**0.5)+1):
                if c % j == 0:
                    isPrime[c] = False
                    break
            else:
                isPrime[c] = True
        if isPrime[other] == -1:
            for j in range(2,int(other**0.5)+1):
                if other % j == 0:
                    isPrime[other] = False
                    break
            else:
                isPrime[other] = True
                
        if isPrime[c] and isPrime[other]:
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
num = [True]*(100000)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False

for i in int(input()):
  _input = input().split(' ')
  sum = 0
  for i in range(int(_input[0]), int(_input[1])+1):
    if (num[i]) and (num[int((i+1)/2)]):
      sum = sum + 1
  print(sum)

Submission status: Runtime Error

Solution code:
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False

for i in range(Q):
  sum = 0
  if LR[i][0] % 2 == 0:
    for i in range(LR[i][0]+1, LR[i][1]+1, 2):
      if (num[i]) and (num[(i+1)/2]):
        sum = sum + 1
  else:
    for i in range(LR[i][0], LR[i][1]+1, 2):
      if (num[i]) and (num[(i+1)/2]):
        sum = sum + 1
  print(sum)

Submission status: Runtime Error

Solution code:
import numpy as np

sosuu = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
         67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
         139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
         223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
         293, 307, 311, 313]


def sosuu_hantei(candidate):
    if candidate == 1:
        return False

    for i in sosuu:
        if candidate <= i:
            return True
        if candidate % i == 0:
            return False
    return True


def getInput():
    """

    :return: list of list of str. 1st dim: row, 2nd dim: column.
    """
    separator = ' '
    ret_array = []
    while True:
        try:
            row = input().split(sep=separator)
            ret_array.append(row)
        except EOFError:
            break
    return ret_array


if __name__ == "__main__":
    g = getInput()
    Q = int(g[0][0])
    l = np.zeros(Q, dtype=np.int32)
    r = np.zeros(Q, dtype=np.int32)
    for i in range(Q):
        l[i] = np.int32(g[i+1][0])
        r[i] = np.int32(g[i+1][1])
    minimum = np.min(l)
    maximum = np.max(r)

    sosuu_hantei_accum = np.zeros(maximum-minimum+1, dtype=np.int32)
    for i in range(maximum-minimum+1):
        if i == 0:
            sosuu_hantei_accum[i] = (sosuu_hantei(minimum+i) and (minimum+i)%2!=0 and sosuu_hantei((minimum+i+1)/2))
        else:
            sosuu_hantei_accum[i] = sosuu_hantei_accum[i-1] + (sosuu_hantei(minimum+i) and (minimum+i)%2!=0 and sosuu_hantei((minimum+i+1)/2))

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

Submission status: Runtime Error

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
            break
    for j in range(len(Nl))
        if Nl[j - 1] <= R[i][1] < Nl[j]:
            tmp2 = j
            break
    print(tmp2 - tmp1)

Submission status: Runtime Error

Solution code:
def prime(n):
  num = [True]*n
  num[0] = num[1] = False
  for i in xrange(2,int(n**0.5)+1):
    if num[i]:
      for j in xrange(i**2, n, i):
        num[j] = False
        return [i for i in xrange(2,n) if num[i]]

Q = int(input())
LR = []
max = 0
for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

prime = prime(max)

for i in range(Q):
  sum = 0
  for num in range(LR[i][0], LR[i][1]+1):
    if (num in prime) and ((num+1) / 2 in prime):
      sum = sum + 1
  print(sum)

Q = int(input())
LR = []
max = 0
for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < int(_input[1]):
    max = int(_input[1])

prime = prime(max)

for i in range(Q):
  sum = 0
  for num in range(LR[i][0], LR[i][1]+1):
    if (num in prime) and ((num+1) / 2 in prime):
      sum = sum + 1
  print(sum)

Submission status: Runtime Error

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):
            print(j)
            prime[j] = False

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

Submission status: Runtime Error

Solution code:
import re
import math
num = int(input())
sosuu = [2]
max = 200
for i in range(3,max,2):
    flag = 1
    flag2 = 0
    for j in sosuu:
        if(j > math.sqrt(i)):
            flag2 += 1
        if(flag2>2):
            break
        if(i % j == 0):
            flag = 0
            break
    if(flag):
        sosuu.append(i)
# print(len(sosuu))
binsosuu = [0 for a in range(max)]
binbinsosuu = [0 for a in range(max)]
sumsosuu = [0 for a in range(max)]
butu = []
for i in sosuu:
    binsosuu[i] = 1
for i in range(1,max,2):
    if(binsosuu[i] + binsosuu[int((i+1)/2)] == 2):
        binbinsosuu[i] = 1
        # print(i)
        butu.append(i)
for i in range(max):
    sumsosuu[i] = sumsosuu[i-1] + binbinsosuu[i]
# print(butu)
# print(binsosuu)
# print(binbinsosuu)
# print(sumsosuu)
# print(sumsosuu[51])
# print(sumsosuu[19])
for i in range(num):
    x,y = map(int,input().split(" "))
    # print("---",sumsosuu[y],sumsosuu[x])
    if(x==y):
        if(binbinsosuu[x]==1):
            print(1)
        else:
            print(0)
    else:
        # if(sumsosuu[y]-sumsosuu[x] == 0 and sumsosuu[x]>0):
        #     print(1)
        # else:
        print(sumsosuu[y]-sumsosuu[x]+binbinsosuu[y]+binbinsosuu[x])

Submission status: Runtime Error

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//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: Runtime Error

Solution code:
def showPrimeNum(N):
	""" N以下の素数を返すプログラム """
	#素数でない場所に1をつけていくだけ
	is_prime_table = [0] * (N+1) 
	is_prime_table[1] = 0
	prime_list = []

	for i in range(2,N//2+1):
		if is_prime_table[i] == 0:
			j = 2 * i	#イテレータ初期化
			while (j <= N):
				is_prime_table[j] = 1
				j += i 		#掛け算より足し算の方が、計算コストが少なくて良い

	for i in range(1,N+1):
		if is_prime_table[i] == 0:
			prime_list.append(i)

	return prime_list


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(" "))
	sign = 0
	for j in range(672):
		if ans[j] >= l and sign == 0:
			l_i = j
			sign = 1

		if ans[j] >= r:
			r_i = j
			break

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