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:
#ABC084D
def main():
    import sys
    Q = int(sys.stdin.readline())
    LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    #print(LR)
    
    check = [1 for _ in range(10**5+1)]
    check[0], check[1] = 0, 0
    for i in range(2, 10**5+1):
        if check[i] ==0:
            continue
        elif check[i] ==1:
            for j in range(2*i, 10**5+1, i):
                check[j] =0
    check2 = check.copy()
    for i in range(2, 10**5+1):
        if check[i]==1:
            #print((i+1)/2, check[(i+1)//2])
            if (i+1)%2==0 and check[(i+1)//2] ==1:
                continue
            else:
                check2[i] = 0
    
    #print(check)
    for lr in LR:
        #print(lr[0], lr[1])
        print(check2[lr[0]:lr[1]+1].count(1))
                


if __name__ =='__main__':
    main()

Submission status: Runtime Error

Solution code:
def calc_prime(n):
    primes = set(list(range(3, n, 2)))
    primes.add(2)
    for a in range(3, n, 2):
        for i in range(a, n):
            x = a * i
            if x >= n:
                break
            if x in primes:
                primes.remove(x)

    return primes


def collect_likes(ps):
    likes = set([p for p in ps if (p + 1) / 2 in ps])
    return likes


def line(xs, n):
    ps = list(xs)
    ps.sort()
    cs = [0] * n
    s = 0
    for i in range(n):
        if i in xs:
            cs[i] = s
            s += 1
        else:
            cs[i] = s

    return cs


def main():
    n = 10 ** 5
    primes = calc_prime(n)
    likes = collect_likes(primes)
    cums = line(likes, n)
    #print(sorted(list(primes))[:100])
    #print(sorted(list(likes))[:100])
    #print(cums[:10])

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


main()

Submission status: Runtime Error

Solution code:
def calc_prime(n):
    primes = set(list(range(3, n, 2)))
    primes.add(2)
    for a in range(3, n, 2):
        for i in range(a, n):
            x = a * i
            if x >= n:
                break
            if x in primes:
                primes.remove(x)

    return primes


def collect_likes(ps):
    likes = set([p for p in ps if (p + 1) / 2 in ps])
    return likes


def line(xs, n):
    ps = list(xs)
    ps.sort()
    cs = [0] * n
    s = 0
    for i in range(n):
        if i in xs:
            cs[i] = s
            s += 1
        else:
            cs[i] = s

    return cs


def main():
    n = 10 ** 5
    primes = calc_prime(n)
    likes = collect_likes(primes)
    cums = line(likes, n)
    #print(sorted(list(primes))[:100])
    print(sorted(list(likes))[:100])
    #print(cums[:10])

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


main()

Submission status: Runtime Error

Solution code:
def main():
    import math
    def generate_primes(num):
        if num == 1: return []
        primes = list(range(2, num + 1))
        i, p = 0, 1
        while p <= math.sqrt(num):
            if primes[i] != 0:
                p = primes[i]
                primes = [prime if (prime % p != 0 or prime == p) else 0 for prime in primes]
            i += 1
        return set([p for p in primes if p != 0])

    primes = generate_primes(100000)
    ans = [0] * 50000
    for j in range(1, 50000):
        i = 2 * j - 1
        if i in primes and (i + 1) / 2 in primes:
            ans[j] = ans[j - 1] + 1
        else:
            ans[j] = ans[j - 1]
    q = int(input())
    for _ in range(q):
        l, r = list(map(lambda x: (int(x) + 1) // 2, input().split()))
        print(ans[r] - ans[l - 1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
input = sys.stdin.readline
MAX = 10**5
N = [0]*((MAX+1)//2)

time = 0
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

n = int(input())
sosuu = eratosthenes((MAX+1)//2)

total = 0
mae = sosuu[0]
for s in sosuu:
    for i in range(mae,s):
        N[i] = total
    if (s+1) // 2 in sosuu:
        total += 1
    mae = s

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

Submission status: Runtime Error

Solution code:
import sys
import math
input = sys.stdin.readline
MAX = 10**5
N = [0]*((MAX+1)//2)

def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

n = int(input())
sosuu = eratosthenes((MAX+1)//2)

total = 0
mae = sosuu[0]
#sosuu = sosuu[0:]
for s in sosuu:
    for i in range(mae,s):
        N[i] = total
    if (s+1) // 2 in sosuu:
        total += 1
    mae = s

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

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))

n  = ri()
lq = [rl() for _ in range(n)]
dp = [-1] * (2017+1)
def is_prime(x):
    if x == 1:
        return False
    else:
        for i in range(3, int(x*0.5)+1, 2):
            if x % i == 0:
                return False
        else:
            x = (x+1)//2
            for i in range(2, int(x*0.5)+1):
                if x % i == 0:
                    return False
            else:
                return True

for li in lq:
    l, q = li
    cnt = 0
    for i in range(l, q+1, 2):
        if dp[i] == 0:
            continue
        elif dp[i] == 1:
            cnt += 1
            continue
        elif is_prime(i):
            dp[i] = 1
            cnt += 1
            continue
        else:
            dp[i] = 0
            continue
    print(cnt)

Submission status: Runtime Error

Solution code:
import bisect
from collections import defaultdict

q = int(input())


n = 10**5 + 1
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 = list(primes)


def is_prime(i):
    p = bisect.bisect_left(primes, i)
    if primes[p] == i:
        return True
    else:
        return False


memo = defaultdict(bool)


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    for i in range(l, r + 1, 2):
        if i in memo:
            tmp += memo[i]
        else:
            memo[i] = is_prime(i) and is_prime((i + 1) // 2)
            tmp += memo[i]
    ans.append(tmp)

print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
import bisect

q = int(input())


n = 100000
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 = list(primes)


def is_prime(i):
    p = bisect.bisect_left(primes, i)
    if primes[p] == i:
        return True
    else:
        return False


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    tmp += sum([is_prime(x) and is_prime((x + 1) // 2) for x in range(l, r + 1, 2)])
    ans.append(tmp)

print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
import math

Q = int(input())
sosu = set(2)

for L in range(3, 10**5, 2): # 2 以外の素数は奇数なので
    for L2 in sosu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosu.add(L)


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

for l,r in li:
    ans = 0
    for x in range(l, r+1):
        if x % 2 == 1:
            if x in sosu and (x+1)/2 in sosu:
                ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
#ABC084D
def main():
    import sys
    Q = int(sys.stdin.readline())
    LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    #print(LR)
    
    def calc(N):
        import math
        for i in range(3, int(math.sqrt(N))+1):
            while N % i==0:
                N =N//i
                return 0
        else:
            num = (N+1)//2
            #if num ==2:
                #return N
            for j in range(2, int(math.sqrt(num)+1)):
                while num % j==0:
                    num = num//j
                    return 0
            else:
                return N
    
     
    L = []
    for i in range(3, 10**5+1, 2):
        tmp = calc(i)
        if tmp !=0:
            L+=[tmp]
    #print(L)
    import bisect
    
    for row in LR:
        l = bisect.bisect_left(L, row[0])
        r = bisect.bisect_right(L, row[1])
        print(r-l)

if __name__=='__main__':
    main(

Submission status: Runtime Error

Solution code:
import bisect

def primetable(n):
  list = [True for _ in range(n + 1)]
  i = 2
  while i * i <= n:
    if list[i]:
      j = i + i
      while j <= n:
        list[j] = False
        j += i
    i += 1
  table = [i for i in range(n + 1) if list[i] and i >= 1]
  return table

prime = primetable(10 ** 5)
accume = [0] * (len(prime))
con = 0

for i,p in enumerate(prime):
  if p <= 2:
    continue
  q = (p + 1) // 2
  if q in prime:
    con += 1
  accume[i] = con

Q = int(input())

for i in range(Q):
  l,r = map(int,input().split())
  if l == 1:
    l += 1
  R = bisect.bisect_left(prime,r)
  L = bisect.bisect_left(prime,l)
  print(accume[R] - accume[L - 1])

Submission status: Runtime Error

Solution code:
import sympy
def mips():
    return map(int,input().split())
def ii():
    return int(input())
Q = ii()
S = [0 for i in range(10 ** 5 + 1)]
N = 0
for i in [j for j in range(1,10 ** 5 + 1)]:
    if sympy.isprime(i) and sympy.isprime((i+1)//2):
        N += 1
        S[i] = N
    else:
        S[i] = N
for i in range(Q):
    l,r = mips()
    print(S[r]-S[l-1])

Submission status: Runtime Error

Solution code:
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

q = int(input())
n = 100000
ass = primes(n)
lkn = []
for p in ass:
    l = (p + 1) // 2
    if l in ass:
        lkn.append(p)
cnt = 0
pre = 1
ans = {}
for p in lkn:
    for i in range(pre,p,2):
        ans[i] = cnt
    cnt += 1
    pre = p
for i in range(q):
    l,r = map(int,input().split())
    l = max(l-2,1)
    print(ans[r] - ans[l])
    #print(ans[r],ans[l])
#print(lkn)

Submission status: Runtime Error

Solution code:

import bisect

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

for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, n + 1, i):
        is_prime[j] = False

is_simular_2017 = is_prime.copy()

for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if not is_prime[(i + 1) // 2]:
            is_simular_2017[i] = False


simular_2017 = [i for i in range(len(is_simular_2017)) if is_simular_2017[i]]

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

for l, r in LR:
    count = 0
    insert_index1 = bisect.bisect_left(simular_2017, l)
    insert_index2 = bisect.bisect_left(simular_2017, r)
    cnt = insert_index2 - insert_index1
    if simular_2017[insert_index2] == r:
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
import bisect

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

for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, n + 1, i):
        is_prime[j] = False

is_simular_2017 = is_prime.copy()

for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if not is_prime[(i + 1) // 2]:
            is_simular_2017[i] = False


simular_2017 = [i for i in range(len(is_simular_2017)) if is_simular_2017[i]]

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

for l, r in LR:
    count = 0
    insert_index1 = bisect.bisect_left(simular_2017, l)
    insert_index2 = bisect.bisect_left(simular_2017, r)
    if insert_index2 - insert_index1 != 0:
        print(insert_index2 - insert_index1)
    else:
        print(1 if l == simular_2017[insert_index1] else 0)

Submission status: Runtime Error

Solution code:

import bisect

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

for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, n + 1, i):
        is_prime[j] = False

is_simular_2017 = is_prime.copy()

for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if not is_prime[(i + 1) // 2]:
            is_simular_2017[i] = False


simular_2017 = [i for i in range(len(is_simular_2017)) if is_simular_2017[i]]

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

for l, r in LR:
    count = 0
    insert_index1 = bisect.bisect_left(simular_2017, l)
    insert_index2 = bisect.biaect_left(simular_2017, r)
    if insert_index2 - insert_index1 != 0:
        print(insert_index2 - insert_index1)
    else:
        print(1 if l == simular_2017[insert_index1] else 0)

Submission status: Runtime Error

Solution code:
q=int(input())
r_max=10**3
t=[0]*r_max
u=[0]*r_max

pn=[2]
t[2]=1
u[2]=1

for L in range(3,r_max):
    chk=True
    for L2 in pn:
        if L%L2 == 0:
          chk=False
          t[L]=t[L-1]
          u[L]=u[L-1]
    if chk==True:
      pn.append(L)
      t[L]=t[L-1]+1
      if (L+1)//2 in pn:
        u[L]=u[L-1]+1
      else:
        u[L]=u[L-1]
  
#print(pn)
#print(t)
#print(u)

for i in range(q):
  l,r=list(map(int,input().split()))
  print((u[r-1]-u[l-1]) if l!=1 else u[r-1]-u[l-1]-1)

Submission status: Runtime Error

Solution code:
import sympy
Q = int(input())
l_r = [list(map(int, input().split())) for _ in range(Q)]

def like(x):
    if sympy.isprime(x) and sympy.isprime((x+1)//2):
        return True
    
    return False

x_list = [0] * (10 ** 5)
for i in range(1, 10**5, 2):
    if like(i):
        x_list[i] = 1

for i in range(Q):
    print(sum(x_list[l_r[i][0]: l_r[i][1]+1]))

Submission status: Runtime Error

Solution code:
N = int(input())
MAX=11000
S = [_+2 for _ in range(MAX)]
old = S
i = 0
while True:
  new = set([])
  t = old[i]
  for j in range(len(old)):
    if old[j] == t or old[j]%t != 0:
      new.add(old[j])
  if len(old) == len(new):
    break
  old = list(new)
  old.sort()
  i += 1


#print(old)
A = [0 for _ in range(MAX)]  
for i in range(MAX):
  if i%2 == 0:
    continue
  if i in new and (i+1)//2 in new:
    A[i] = 1
SUM = [0 for _ in range(MAX)] 
for i in range(1,MAX):
  SUM[i] += A[i]+SUM[i-1]
#print(SUM)

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

Submission status: Runtime Error

Solution code:
q = int(input())
l, r = [0]*q, [0]*q
for i in range(q):
    l[i], r[i] = map(int, input().split())

MAX = 101010
is_prime = [1]*MAX
is_prime[0] = 0
is_prime[1] = 0
for i in range(2,MAX):
    if not is_prime[i]: 
        continue
    for j in range(i*2, MAX, i):
        is_prime[j] = 0

a = [0]*MAX
for i in range(MAX,,2):  # ,,2
    # if i%2 == 0: 
    #     continue
    if is_prime[i] and is_prime[(i+1)//2]: 
        a[i] = 1

s = [0]*(MAX+1)
for i in range(MAX): 
    s[i+1] = s[i] + a[i]

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

Submission status: Runtime Error

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

def primes(n):
    isp = [True for _ in range(n+1)]
    isp[0] = False
    isp[1] = False
    l = ceil(sqrt(n))
    n += 2
    i = 4
    while i < n:
        isp[i] = False
        i += i
    for i in range(3, l, 2):
        if not isp[i]:
            continue
        for j in range(i*2, n, i):
            isp[j] = False
    return isp

q = int(input())
maxv = 10**5
isp = primes(maxv)
cnt = [0 for _ in range(maxv + 1)]

ans = 0
for i in range(3, maxv+1):
    if i%2 and isp[i] and isp[(i+1)//2]:
        cnt[i] = 1
acc = list(accumulate(cnt))
for _ in range(q):
    l, r = map(int, input().split())
    print(acc[r] - acc[l-1])

Submission status: Runtime Error

Solution code:
import itertools

def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return table

prime = sieve(5*10**4)
acu = [0] * ((5*10**4)//2+1)
for i in range(1,(5*10**4)//2+1):
    k = (i-1) * 2 +1
    if k in prime and (k+1)//2 in prime:
        acu[i] = acu[i-1] + 1
    else:
        acu[i] = acu[i-1]

q = int(input())

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

Submission status: Runtime Error

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

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

prime = []
ans = [0]*10001
sum_a = [0]*10001
for n in range(1, 10000+1):
  if is_prime(n) and is_prime((n+1)//2):
    if n != 2:
      prime.append(n)
      ans[n] = 1
  sum_a[n] = sum_a[n-1] + ans[n]

for l, r in query:
  print(sum_a[r] - sum_a[l-1])

Submission status: Runtime Error

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

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

prime = []
ans = [0]*10001
sum_a = [0]*10001
for n in range(3, 10000):
  if is_prime(n) and is_prime((n+1)//2):
    prime.append(n)
    ans[n] = 1
  sum_a[n] = sum_a[n-1] + ans[n]

for l, r in query:
  print(sum_a[r] - sum_a[l-1])

Submission status: Runtime Error

Solution code:
numbers_like_2017 = [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 _ in range(Q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(numbers_like_2017, r) - bisect.bisect_left(numbers_like_2017, l))

Submission status: Runtime Error

Solution code:
def eratosthenes(limit):
    import math
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    while True:
        prime = min(A)
        if prime > math.sqrt(limit): break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A: P.append(a)
    return P
L = eratosthenes(10**5)
ans = [0]*(10**5+1)
d = [0]*(10**5+1)
for i in l: d[i] += 1
for i in range(2, 10**5+1):
    ans[i] += ans[i-1]
    if i%2==1 and d[(i+1)//2]: ans[i] += 1
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])

Submission status: Runtime Error

Solution code:
import math
Q = int(input())

l = [0 for i in range(Q)]
r = [0 for i in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = 100001#max(r)+1
  
  prime = [1 for i in range(MAXI)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for i in range(MAXI+1)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] = (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = 0 #even
  return sn

base = create_list()
#print(base)
for i in range(Q):
  if(l[i]==r[i]):
    print(base[l[i]])
  else:
    lnum = base[0:l[i]]
    rnum = base[0:r[i]]
    print( sum(rnum)-sum(lnum) )

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    Q=int(input())
    # n以下の素数のリストprimes
    n = 10**5
    primes = set(range(2, n + 1))

    # 合成数 x は p<=x**0.5を満たす素因子 p をもつという性質を利用
    for i in range(2, int(n ** 0.5 + 1)):
        primes.difference_update(range(i * 2, n + 1, i))
    primes = list(primes)
    A = [0] * (10 ** 5 + 1)

    for j in range(1,10**5+1,2):
        if j in primes and (j+1)//2 in primes:
            A[j]=1
        # 累積和を格納したリスト．A[l:r]の総和はB[r] - B[l]
    B = list(accumulate(A))


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




resolve()

Submission status: Runtime Error

Solution code:
import math
from itertools import accumulate
def is_prime(n):
  if n==2:
    return True
  for i in range(2,int(math.sqrt(n)+1)):
    if n%i==0:
      return False
  return True
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
  l[i],r[i]=map(int,input().split())
min_l=min(l)
max_r=max(r)
a=[]
for i in range(min_l,max_r+1):
  if i%2==0:
    a.append(0)
  else:
    if is_prime(i) and is_prime((i+1)/2):
      a.append(1)
check=[0]+a
check=list(accumulate(check))
for i in range(q):
  print(check[r[i]-min_l+1]-check[l[i]-min_l])

Submission status: Runtime Error

Solution code:
import math
from itertools import accumulate
def is_prime(n):
  if n==2:
    return True
  for i in range(2,int(math.sqrt(n)+1)):
    if n%i==0:
      return False
  return True
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
  l[i],r[i]=map(int,input().split(""))
min_l=min(l)
max_r=max(r)
a=[]
for i in range(min_l,max_l+1):
  if i%2==0:
    a.append(0)
  else:
    if is_prime(n) and is_prime((i+1)/2):
      a.append(1)
check=[0]+check
check=list(accumulate(check))
for i in range(q):
  print(check(r[i+1])-check(l[i]))

Submission status: Runtime Error

Solution code:
import bisect
import math
import sys
from bisect import bisect_left
from math import ceil, sqrt

q = int(sys.stdin.readline().rstrip())
lr = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(q)]


def era_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))
    primes = [n for n in range(N+1) if temp[n]]
    return primes


primes = era_prime(100000)
post_primes = []
ind = 0
tmp = 0
p = [0]
for pi in primes:
    if (pi + 1) // 2 in primes:
        post_primes.append(pi)

for i in range(1, 100000):
    if ind >= len(post_primes):
        break
    if i == post_primes[ind]:
        tmp += 1
        ind += 1
    p.append(tmp)
for lri in lr:
    ans = 0
    print(p[lri[1]]-p[lri[0]-1])

Submission status: Runtime Error

Solution code:
import math
import sys
from bisect import bisect_left
from math import ceil, sqrt

q = int(sys.stdin.readline().rstrip())
lr = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(q)]


def era_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))
    primes = [n for n in range(N+1) if temp[n]]
    return primes


primes = era_prime(100000)
post_primes = []
for pi in primes:
    if (pi + 1) // 2 in primes:
        post_primes.append(pi)


for lri in lr:
    l = bisect_left(post_primes, lri[0])
    r = bisect_left(post_primes, lri[1])
    ans = r - l
    # if post_primes[l] == post_primes[r] and post_primes[l] in lri:
    #     ans += 1
    if post_primes[r] in lri:
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
from itertools import accumulate

def read():
    return sys.stdin.readline().rstrip()

def main():
    n = 10**5
    p = [i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0 for i in range(n + 1)]
    p[1] = False
    p[2] = p[3] = p[5] = p[7] = True
    for pi in range(3, int(n ** 0.5) + 1, 2):
        if not p[pi]:
            continue
        for i in range(pi ** 2, n + 1, pi):
            p[i] = False
    like = [i % 2 == 1 and p[i] and p[(i + 1) // 2] for i in range(n)]
    a = list(accumulate(like[1:], initial=0))
    for _ in range(int(read())):
        l, r = map(int, read().split())
        print(a[r] - a[l - 1])

if __name__ == '__main__':
    main()