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:
import sys
import bisect
import math
input = sys.stdin.readline

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

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]
        
for t in l:
    x, y = t[0], t[1]
    p = 0
    if 0 <= x - 1:
        p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Runtime Error

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

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

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]
        
for t in l:
    x, y = t[0], t[1]
    p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Runtime Error

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

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

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]
        
for x, y in l:
    p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Runtime Error

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

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

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]
        
for x, y in l:
    p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Runtime Error

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

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

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        cum[i] = cum[i - 1]
        
for t in l:
    x, y = 0, 0
    try:
        x, y = t
    except:
        print
    p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Runtime Error

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

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

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        cum[i] = cum[i - 1]
        
for x, y in l:
    p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Runtime Error

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

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

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        cum[i] = cum[i - 1]
        
for x, y in l:
    p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Runtime Error

Solution code:
q=int(input())
l=[0]
c=0
def prime(n):
  if n==2:
    return True
  elif n==1:
    return False
  else:
    return pow(2,n-1,n)==1
for i in range(1,100001):
  if prime(n)==True and prime((n+1)//2)=True:
    c+=1
  l.append(c)
for i in range(q):
  a,b=map(int,input().split())
  print(l[b]-l[a-1])

Submission status: Runtime Error

Solution code:
def eratosthenes_2017like(x): #エラトステネスからちょっと変更
    prime = []
    if x < 3:
        return prime
    search = [i for i in range(2,x+1)]
    while search[0] <= math.sqrt(x):
        add = search.pop(0)
        prime.append(add)
        multiple = 1
        while add*multiple <= x:
            multiple += 1
            if add*multiple in search:
                search.remove(add*multiple)
    prime.extend(search)

    for p in prime[::-1]:
        if not((p+1)/2 in prime):
            prime.remove(p)
    return prime

for i in range(q):
    l, r = map(int,input().split())
    left_len = len(eratosthenes_2017like(l-1))
    right_len = len(eratosthenes_2017like(r))
    print(right_len - left_len)

Submission status: Runtime Error

Solution code:
def eratosthenes_2017like(x):
    prime = []
    if x < 3:
        return prime
    search = [i for i in range(2,x+1)]
    while search[0] <= math.sqrt(x):
        add = search.pop(0)
        prime.append(add)
        multiple = 1
        while add*multiple <= x:
            multiple += 1
            try:
                search.remove(add*multiple)
            except ValueError:
                pass
    prime.extend(search)

    for p in prime[::-1]:
        if not((p+1)/2 in prime):
            prime.remove(p)
    return prime

for i in range(q):
    l, r = map(int,input().split())
    left_len = len(eratosthenes_2017like(l-1))
    right_len = len(eratosthenes_2017like(r))
    print(right_len - left_len)

Submission status: Runtime Error

Solution code:
import math

# 0以上整数x「未満」の素数をリストに格納して返す
c=[1]*100005
c[0]=c[1]=0

for i in range(2,10005):
    if(c[i]):
        for j in range(i*i,10005,i):
            c[j]=0

a=[0]*100005
for i in range(3,10005,2):
    if(c[i] and c[(i+1)//2]):
        a[i]=1
for i in range(1,10004):
    a[i+1]+=a[i]

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

Submission status: Runtime Error

Solution code:
import math
from itertools import accumulate

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

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0
    return 1

Q = int(input())
L = [0]*Q
R = [0]*Q

for j in range(Q):
    L[j],R[j] = [int(i) for i in input().split()]

li = []
for i in range(min(L),max(R)+1,1):
    if i%2 == 1:
        li.append(is_prime(i) * is_prime((i+1)//2))
    else:
        li.append(0)

ans = [0]
ans += list(itertools.accumulate(li))

for i,j in zip(L,R):
    print(ans[j-min(L)+1] - ans[i-min(L)])

Submission status: Runtime Error

Solution code:
q = int(input())
a = [list(int(i) for i in input().split()) for i in range(q)]
MAX = 10**5
is_prime = [1]*MAX
for i in range(2, MAX):
    if not is_prime[i]:
        continue
    for j in range(i*2, MAX, i):
        is_prime[j] = 0
s = [0]*MAX
for i in range(3,MAX):
    s[i] = s[i-1] + 1 if is_prime[i] and is_prime[(i+1)//2]
for i in range(q):
    l,r = a[i]
    print(s[r]-s[l-1])

Submission status: Runtime Error

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

def is_prime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

for i in range(Q):
    sum = 0
    for j in range(l[i][0],l[i][1]+1):
        if is_prime(j) and is_prime((j+1)//2):
            sum +=1
        else:
            continue
    print(sum)

Submission status: Runtime Error

Solution code:

import math
import bisect


prime = [2,3,5,7,11,13,17,19]
for i in range(prime[-1]+2,100000,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if x < p:
            break;

        if i % p == 0:
            found = True
            break
                
    if not found:
        prime.append(i)


#print(prime)
#import matplotlib.pyplot as plt
#size = 10000
#plt.scatter(range(0,size),prime[0:size])
#plt.plot(prime)
#plt.show()

for i in range(len(prime)):
#    if 2.5*i - 1< prime[i]:
#       continue

    if prime[i] <11 *i + 3:
        continue

    print(prime[i])



q = int(input())

def low(x:int)->int:
    x = (x -3)// 11
    return x if x>0 else 0

def hi(x:int)->int:
    return int( (x+1)//2.5) + 1

for _ in range(q):

    l, r = map(int,input().split())
 #   l += 1 if l%2 == 0 else 0

#    print((l,r))

    ans = 0
    for i in range( l , r+1, 2):

        low_1 = low(i)
        hi_1 = hi(i)

        #print((low_1,hi_1))
        xi = bisect.bisect_right(prime, i,lo = low_1,hi = hi_1)
        #print(xi)
        p1 = prime[xi-1]
        if p1 != i:
            continue

        i2 = (i+1)//2
        low_2 = low(i2)
        hi_2 = hi(i2)

        yi = bisect.bisect_right(prime, i2,lo = low_2, hi = min(hi_2,xi) )
        if prime[yi-1] != i2:
            continue

        ans += 1

    print(ans)

Submission status: Runtime Error

Solution code:
def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1
d=[]
n=10**5+1
for i in range(2,n):
    if prime_t(i):
        d.append(i)
 
q=int(input())
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r+1,2):
        if (j in d and (j+1)//2 in d): ans+=1
    print(ans)
def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1
d=[]
n=10**5+1
for i in range(2,n):
    if prime_t(i):
        d.append(i)

q=int(input())
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r+1,2):
        if (j in d and (j+1)//2 in d): ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
import bisect

Q = int(input())

L = [1 for i in range(100001)]
L[0] = 0
L[1] = 0
for i in range(100001):
	if L[i] == 1:
		c = 2
		while True:
			if i * c <= 100000:
				L[i * c] = 0
				c += 1
			else:
				break
p2017 = []
for i in range(3, 100001):
	if i % 2 != 0:
		if L[i] == 1 and L[int((i + 1) // 2)] == 1:
			p2017.append(i)

for i in range(Q):
	l, r = list(map(int, input().split()))
	a = bisect.bisect_left(p2017, l)
	b = bisect.bisect_left(p2017, r)
	if p2017[b] == r:
		b += 1
	print(b - a)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def check(n):
        if n == 1:
            return False
        i = 2
        while i*i <= n:
            if n%i == 0:
                return False
            i += 1
        return True
    f = [0 for i in range(10001)]
    for i in range(1,10001):
        f[i] += f[i-1]
        if check(i):
            if check((i+1)//2):
                f[i] += 1
    q = I()
    for i in range(q):
        l,r = LI()
        print(f[r]-f[l-1])

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Runtime Error

Solution code:
# D
N = 10**5
primes = set([])
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, N+1):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, N//i+1):
            is_prime[j*i] = False
    
# like-2017
cnt = [0]*(N+2)
for i in range(1, N+2):
    cnt[i] += cnt[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt[i] += 1
#print(cnt[:100])
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])

Submission status: Runtime Error

Solution code:
n = (int)(input())
s = []
t = []
for _ in range(n):
    a, b = (list)(map(int, input().split()))
    s.append(a)
    t.append(b)
mi = min(s)
ma = max(t)


def primeList(N):
    max = int(N//2)+5
    seachList = [i for i in range(2, N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


def prime(s, t):
    primes = primeList(t)
    l = [0]*(t+1)
    c = 0
    s = 0
    for i in range(s, t+1):
        if i in primes and (i+1)//2 in primes:
            c += 1
        l[i] = c
    return l


primes = prime(mi, ma)
for i in range(n):
    print(primes[t[i]] - primes[s[i]-1])

Submission status: Runtime Error

Solution code:
from sympy import isprime
n = (int)(input())
s = []
t = []
for _ in range(n):
    a, b = (list)(map(int, input().split()))
    s.append(a)
    t.append(b)
mi = min(s)
ma = max(t)


def isPrime(i):
    return isprime(i)


def prime(s, t):
    l = [0]*(t+1)
    c = 0
    s = 0
    for i in range(s, t+1):
        if isPrime(i) and isPrime((i+1)//2):
            c += 1
        l[i] = c
    return l


primes = prime(mi, ma)

for i in range(n):
    print(primes[t[i]] - primes[s[i]-1])

Submission status: Runtime Error

Solution code:
import bisect

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

def prime_list(max_num):
    prime_list = [2]
    for n in range(1,max_num+1,2):
        if n == 1:
            continue
        else:
            if prime_num(n):
                prime_list.append(n)
    return prime_list

prime_list = prime_list(10**5)

Q = int(input())

for i in range(Q):
    l,r = map(int, input().split())
    ans = 0
    for n in range(l,r+1,2):
        #check
        tar1 = n
        tar2 = (n+1)//2

        ind1 = bisect.bisect_left(prime_list, tar1,0,len(prime_list))
        ind2 = bisect.bisect_left(prime_list, tar2,0,len(prime_list))

        if tar1 == prime_list[ind1] and tar2 == prime_list[ind2]:
            ans += 1
    print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
p,q,r = [2],[],[]
k = 3
while k < 100000:
  flag = True
  for t in p:
    if t*t > k:
      break
    if k%t == 0:
      flag = False
  if flag:
    p.append(k)
  k += 2
for t in p[1:]:
  if (t+1)//2 in p:
    q.append(t)
q.append(100000+3)
k = 0
for i in range(99999//2):
  while q[k]<=2*i+1:
    k += 1
  r.append(k)
c = int(input())
while c>0:
  x,y = map(int,input().split())
  print(r[y//2]-r[max(x,3)//2-1])
  c -= 1

Submission status: Runtime Error

Solution code:
k = 3
p,q,r = [2],[],[]
while k < 100000:
  flag = True
  for t in p:
    if t*t > k:
      break
    if k%t == 0:
      flag = False
  if flag:
    p.append(k)
  k += 2
for t in p[1:]:
  if (t+1)//2 in p:
    q.append(t)
q.append(100000+3)
k = 0
for i in range(99999//2):
  while q[k]<=2*i+1:
    k += 1
  r.append(k)
for _ in [0]*int(input()):
  x,y = map(int,input().split())
  print(r[y//2]-r[max(x,3)//2-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

'''Snippets for prime.
Available functions:
- is_included: Determine whether it is a prime number.
- generate: Generate a list of prime numbers using sieve of Eratosthenes.
'''


class Prime(object):
    '''Represents a snippet for prime numbers.
    '''

    def __init__(self, number):
        self.number = number
        self._values = []

    def is_included(self) -> bool:
        '''Determine whether it is a prime number.
        Args:
            number: Int of number (greater than 0).
        Returns:
            True if the input number was prime.
            False if the input number was not prime.
        See:
            https://qiita.com/srtk86/items/874639e361917e5016d4
            https://docs.python.org/ja/3/library/2to3.html?highlight=isinstance#2to3fixer-isinstance
        '''

        from math import sqrt

        if (self.number <= 1) or (isinstance(self.number, float)):
            return False

        for i in range(2, int(sqrt(self.number)) + 1):
            if self.number % i == 0:
                return False

        return True

    def generate(self) -> list:
        '''Generate a list of prime numbers using sieve of Eratosthenes.
        Returns:
            A list of prime numbers that is eqaul to or less than the input
            number.
        Landau notation: O(n log log n)
        See:
            https://beta.atcoder.jp/contests/abc110/submissions/3254947
        '''

        if self._values:
            return self._values

        is_met = [True for _ in range(self.number + 1)]
        is_met[0] = False
        is_met[1] = False

        for i in range(2, self.number + 1):
            if is_met[i]:
                self._values.append(i)

                for j in range(2 * i, self.number + 1, i):
                    is_met[j] = False

        return self._values


def main():
    from bisect import bisect_left
    from itertools import accumulate

    q = int(input())
    prime = Prime(10 ** 5)
    primes = prime.generate()
    primes[0] = 0
    like_numbers = list()

    for current_prime in primes:
        prime = Prime((current_prime + 1) // 2)

        if prime.is_included():
            like_numbers.append(1)
        else:
            like_numbers.append(0)

    like_number_count = list(accumulate(like_numbers))

    for i in range(q):
        li, ri = map(int, input().split())
        begin = bisect_left(primes, li)
        end = bisect_left(primes, ri)
        print(like_number_count[end] - like_number_count[begin - 1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
highest = 10004

def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]


accum = [0 for i in range(highest)]
flag = [1 for i in range(highest)]
flag[0] = 0
flag[1] = 0

for i  in range(2,highest//2):
    flag[i*2] = 0

for i in range(3,highest//2):
    if flag[i] == 0:
        accum[i]  = accum[i-1]
    else:
        for j in range(2,highest//i):
            flag[i*j] = 0


        if flag[(i+1)//2] == 0:
            accum[i] = accum[i - 1]
        else:
            accum[i] = accum[i - 1] + 1

for i in range(highest//2, highest):
    if flag[i] == 0:
        accum[i]  = accum[i-1]
    else:
        if flag[(i+1)//2] == 0:
            accum[i] = accum[i - 1]
        else:
            accum[i] = accum[i - 1] + 1

Q = getN()
lrpair = []
for i in range(Q):
    l,r = getMN()
    lrpair.append((l,r))
for pair in lrpair:
    l, r = pair
    print(accum[r] - accum[l-1])

Submission status: Runtime Error

Solution code:
TOP = 10004

def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]


accum = [0 for i in range(TOP)]
flag = [1 for i in range(TOP)]
flag[0] = 0
flag[1] = 0

for i  in range(2,TOP//2):
    flag[i*2] = 0

for i in range(3,TOP//2):
    if flag[i] == 0:
        accum[i]  = accum[i-1]
    else:
        for j in range(2,TOP//i):
            flag[i*j] = 0


        if flag[(i+1)//2] == 0:
            accum[i] = accum[i - 1]
        else:
            accum[i] = accum[i - 1] + 1

for i in range(TOP//2, TOP):
    if flag[i] == 0:
        accum[i]  = accum[i-1]
    else:
        if flag[(i+1)//2] == 0:
            accum[i] = accum[i - 1]
        else:
            accum[i] = accum[i - 1] + 1

Q = getN()
for i in range(Q):
    l,r = getMN()
    print(accum[r] - accum[l-1])

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;


const int N_MAX = 100001;
VI prime;
void generate_prime() {
    prime.push_back(2); 
    FOR(i, 3, N_MAX) {
        for(auto p : prime) {
            if(i % p == 0) break;
            if(p > sqrt(i)) {
                prime.push_back(i);
                break;
            }
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    generate_prime();
    set<int> prime1(ALL(prime));
    set<int> prime2;
    for(auto& p : prime1) {
        if(p == 2) continue;
        if(prime1.count((p + 1) / 2) == 1) prime2.insert(p);
    }
    VI ans(N_MAX);
    ans[0] = 0;
    FOR(i, 1, N_MAX - 1) {
        if(prime2.count(i) == 1) ans[i] = ans[i - 1] + 1;
        else ans[i] = ans[i - 1];
    }
    
    int q;
    cin >> q;
    REP(i, q) {
        int l, r;
        cin >> l >> r;
        cout << ans[r] - ans[l - 1] << '\n';
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np
Q = int(input())

p = np.array([i for i in range(2*10**5+1)])
p[1]=0
for i in range(2,10**5):
    p[2*i::i] = 0
p = p[p!=0]

dic = {i:1 for i in p}

for _ in range(Q):
    l,r = list(map(int,input().split()))
    tmp = p[l<=p]
    tmp = tmp[tmp<=r]
    print(len(tmp[[dic.get((x+1)//2,0)==1 for x in tmp]]))

Submission status: Runtime Error

Solution code:
maxnum = 10100

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

is_like = [False] * maxnum
for i in range(maxnum):
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        is_like[i] =  True

like_sum = [0] * maxnum
for i in range(3, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_like[i]):
        like_sum[i] += 1

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

Submission status: Runtime Error

Solution code:
maxnum = 10000

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

is_like = [False] * maxnum
for i in range(maxnum):
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        is_like[i] =  True

like_sum = [0] * maxnum
for i in range(3, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_like[i]):
        like_sum[i] += 1

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

Submission status: Runtime Error

Solution code:
maxnum = 10000

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

is_like = [False] * maxnum
for i in range(maxnum):
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        is_like[i] =  True

like_sum = [0] * maxnum
for i in range(3, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_like[i]):
        like_sum[i] += 1

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

Submission status: Runtime Error

Solution code:
maxnum = 10001

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

is_like = [False] * maxnum
for i in range(maxnum):
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        is_like[i] =  True

like_sum = [0] * maxnum
for i in range(1, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_like[i]):
        like_sum[i] += 1

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

Submission status: Runtime Error

Solution code:
maxnum = 10000

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

is_like = [False] * maxnum
for i in range(maxnum):
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        is_like[i] =  True

like_sum = [0] * maxnum
for i in range(1, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_like[i]):
        like_sum[i] += 1

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

Submission status: Runtime Error

Solution code:
import bisect
def prime_list(n):
    '''
    n未満の素数のリストを返す
    '''
    num = list(range(2, n))
    prime = []
    while num[0] ** 2 < n:
        p = num.pop(0)
        for j in range(2 * p, n, p):
            if j in num:
                num.remove(j)
        prime.append(p)
    prime += num
    return prime

Q = int(input())
queries = [list(map(int, input().split())) for _ in range(Q)]
primes = prime_list(10 ** 5)
prime_2017like = []
for prime in primes:]
    if (prime + 1) // 2 in primes:
        prime_2017like.append(prime)
for i in range(Q):
    li, ri = queries[i]
    print(bisect.bisect_right(prime_2017like, ri) - bisect.bisect_right(prime_2017like, li - 1))

Submission status: Runtime Error

Solution code:
 
Q = int(input())
 
# 素数表
n = 100000
P = [False] * n
P[2] = True
for i in range(3, n, 2):
    k = True
    for j in range(3, int(math.sqrt(i)) + 1, 2):
        if i % j == 0:
            k = False
            break
    if k:
        P[i] = True
 
# Nと(N+1)÷2が素数か否か
a = [0] * n
for i in range(1, n, 2):
    j = (i + 1) // 2
    if P[i] and P[j]:
        a[i] = 1
# 累積和
for i in range(n - 1):
    a[i + 1] += a[i]
 
for _ in range(Q):
    l, r = map(int, input().split())
    print(a[r] - a[l - 1])