Problem:


Score : 400 points

Problem Statement

We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Sample Input 1

1
3 7

Sample Output 1

2

3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.

5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.

7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.

Thus, the response to the first query should be 2.

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

6
1 53
13 91
37 55
19 51
73 91
13 49

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Accepted

Solution code:
from itertools import takewhile

"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

  @classmethod
  def all_identity(cls, operator, equality, identity, size):
    return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

  @classmethod
  def from_initial_data(cls, operator, equality, identity, data):
    size = 1 << (len(data)-1).bit_length()
    temp = [identity]*(2*size)
    temp[size:size+len(data)] = data
    data = temp

    for i in reversed(range(size)):
      data[i] = operator(data[2*i],data[2*i+1])
    return cls(operator, equality, identity, data)

  # これ使わずファクトリーメソッド使いましょうね
  def __init__(self, operator, equality, identity, data):
    if equality is None:
      equality = lambda a,b: False
    self.op = operator
    self.eq = equality
    self.id = identity
    self.data = data
    self.size = len(data)//2

  def _interval(self, a, b):
    a += self.size
    b += self.size
    ra = self.id
    rb = self.id

    data = self.data
    op = self.op
    while a < b:
      if a & 1:
        ra = op(ra,data[a])
        a += 1
      if b & 1:
        b -= 1
        rb = op(data[b],rb)
      a >>= 1
      b >>= 1
    return op(ra,rb)

  def __getitem__(self, i):
    if isinstance(i, slice):
      return self._interval(
                  0 if i.start is None else i.start,
                  self.size if i.stop is None else i.stop)
    elif isinstance(i, int):
      return self.data[i+self.size]

  def __setitem__(self, i, v):
    i += self.size
    data = self.data
    op = self.op
    eq = self.eq
    while i and not eq(data[i],v):
      data[i] = v
      v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
      i >>= 1

  def __iter__(self):
    return self.data[self.size:]

# 素数生成器
def generate_primes():
  from collections import defaultdict
  from itertools import count
  D = defaultdict(list)

  q = 2
  for q in count(2):
    if q in D:
      for p in D[q]:
        D[p+q].append(p)
      del D[q]
    else:
      yield q
      D[q*q].append(q)

from operator import add,eq

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

m = max(r for l,r in Q)


primes = set(takewhile(lambda x: x <= m, generate_primes()))
primes.remove(2)

A = [0]*(m+1)

for p in primes:
  if (p+1)//2 in primes:
    A[p] = 1

A[3] = 1

T = SegmentTree.from_initial_data(add, eq, 0, A)

for l,r in Q:
  print(T[l:r+1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


import itertools


INT_END = 10 ** 5 + 1


def sieve_of_eratosthenes(end, typecode="L"):
    """Enumerates the prime numbers below the given integer.

    :param int end: Prime numbers below this integer will be enumerated.
    :param str typecode: The type of the array to be returned (optional).
    :return: The array of the prime numbers.
    :rtype: :class:`array.array`
    """

    assert end > 1
    is_prime = [True for i in range(end)]
    is_prime[0] = False
    is_prime[1] = False
    # primes = array.array(typecode)
    for i in range(2, end):
        if is_prime[i]:
            # primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    # return primes
    return is_prime


class CumulativeSum(object):
    """Constructs the cumulative sum of the elements in the given sequence.

    :param sequence: The sequence to be processed.
    :type sequence: sequence
    """

    def __init__(self, sequence):
        self.cumulative_sum = [0]
        self.cumulative_sum.extend(itertools.accumulate(sequence))

    def partial_sum(self, first, last):
        """Computes the partial sum of the sequence.

        :param first: The index representing the first element of the
                      subsequence.
        :type first: int
        :param last: The index representing the last element of the
                     subsequence.
        :return: The partial sum.
        """
        return self.cumulative_sum[last + 1] - self.cumulative_sum[first]


def enumerate_like_number(end=INT_END):
    is_prime = sieve_of_eratosthenes(end)
    is_like = [False for _ in range(end)]
    for i in range(1, end, 2):
        if is_prime[i] and is_prime[(i + 1) // 2]:
            is_like[i] = True
    return is_like


def main():
    q = int(input())
    cs = CumulativeSum(enumerate_like_number())
    for _ in range(q):
        l, r = (int(z) for z in input().split())
        print(cs.partial_sum(l, r))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = (10**5)+5

is_prime = [True for _ in range(N)]
is_prime[1] = False
for i in range(2,N) :
    if not is_prime[i] :
        continue
    j = i*2
    while j<N :
        is_prime[j] = False
        j += i

cnt_acc = [0 for _ in range(N)]
for i in range(1,N) :
    cnt_acc[i] = cnt_acc[i-1]
    if is_prime[i] and is_prime[(i+1)//2] :
        cnt_acc[i] += 1

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

Submission status: Accepted

Solution code:
import math

N = 100001   # N is max number
prime = [True]*(N+1)
prime[0] = False
prime[1] = False

R = int(math.sqrt(N))

for i in range(2, R+1):
    if prime[i]:
        cnt = 2
        while i * cnt <= N:
            prime[i * cnt] = False
            cnt += 1
# if prime[i] = True, i is prime number

def check(n):
    return prime[n] and prime[(n+1)//2]

imos = [0]*(N+2)
for i in range(1, N+1):
    if i % 2 == 1:
        if check(i):
            imos[i] += 1
for i in range(1, N+2):
    imos[i] = imos[i] + imos[i-1]

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

Submission status: Accepted

Solution code:
# list all primes
import numpy as np
ind_prime = np.ones(10**5+1, dtype="int")


max_prime = int(np.ceil(np.sqrt(10**5)))

if max_prime**2 == 10**5:
    max_prime += 1

ind_prime[0] = 0
ind_prime[1] = 0

for i in range(2, max_prime):
    if ind_prime[i] == 1:
        ind_prime[i*i:(10**5+1):i] = 0


ind_like_2017 = np.zeros(10**5+1, dtype="int")
for i in range(1, 10**5+1, 2):
    if ind_prime[i] == 1 and ind_prime[(i+1)//2] == 1:
        ind_like_2017[i] = 1
        
ind_like_2017_cum = ind_like_2017.cumsum()

res_list = []
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    res_list.append(ind_like_2017_cum[r]-ind_like_2017_cum[l-1])
    
for r in res_list:
    print(r)

Submission status: Accepted

Solution code:
sz = int(1e5)
isprime = [True for _ in range(sz + 1)]

for i in range(sz + 1):
    if i <= 1:
        isprime[i] = False
    elif isprime[i]:
        j = 2 * i
        while j <= sz:
            isprime[j] = False
            j += i

cnt = [0 for _ in range(sz + 1)]
for i in range(3, sz + 1):
    if i % 2 == 1 and isprime[i] and isprime[(i + 1) // 2]:
        cnt[i] = cnt[i - 1] + 1
    else:
        cnt[i] = cnt[i - 1]

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

Submission status: Accepted

Solution code:
MAXN = 10**5+10
sieve = [0,0] + [1]*MAXN
m = 2
while m*m <= MAXN:
    if sieve[m]:
        for n in range(2*m,MAXN,m):
            sieve[n] = 0
    m += 1

ok = [0]*MAXN
cums = [0]
for n in range(MAXN):
    if sieve[n] and sieve[(n+1)//2]:
        ok[n] = 1
    cums.append(cums[-1] + ok[n])

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

Submission status: Accepted

Solution code:
from itertools import accumulate
# Eratosthenes
def eratosthenes(n):
    prime_table = [False,False,True]+[False if i%2!=0 else True for i in range(n-2)]
    i=3
    while i*i<=n:
        if prime_table[i]:
            j=i*i
            while j<=n:
                prime_table[j]=False
                j+=i
        i+=2
    return prime_table

pt=eratosthenes(100000)
ok=[0 for i in range(100000)]
i=1
while i<100000:
    if pt[i] and pt[(i+1)//2]:
        ok[i]=1
    i+=2
ok=list(accumulate(ok))

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

a = [0] * 100005

isp = [1] * 100005
isp[0] = isp[1] = 0
for i in range(2, 100005):
    if isp[i]:
        for j in range(i*i, 100005, i):
            isp[j] = 0
for i in range(3, 100005, 2):
    if isp[i] and isp[(i+1)//2]:
        a[i] = 1
for i in range(1, 100004):
    a[i+1] += a[i]

q = ni()
for i in range(q):
    l, r = na()
    print(a[r] - a[l-1])

Submission status: Runtime Error

Solution code:
#  dataArray :
#     2
def i_input(): return int(input())

def i_map(): return map(int, input().split())


#  dataArray :
#     2 3 4
def i_list(): return list(i_map())

#  dataArray :
#     2 3 4 5 6
#     1 2 3 4 5
#     2 3 4 5 6
def i_row_list(N): return [i_list() for _ in range(N)]

import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    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


q=i_input()
rl=i_row_list(q)
naxnum=0
for r,l in rl:
    maxnum=max(r,l,naxnum)

unums=seachPrimeNum(maxnum)

tmprow=[0]*(maxnum+1)
for n in unums:
    if (n+1)/2 in unums:
        tmprow[n]=1

for i in range(len(tmprow)):
    if i !=0:
        tmprow[i]=tmprow[i]+tmprow[i-1]


for r,l in rl:
    num=tmprow[l]-tmprow[r-1]
    print(num)

Submission status: Runtime Error

Solution code:
#  dataArray :
#     2
def i_input(): return int(input())

def i_map(): return map(int, input().split())


#  dataArray :
#     2 3 4
def i_list(): return list(i_map())

#  dataArray :
#     2 3 4 5 6
#     1 2 3 4 5
#     2 3 4 5 6
def i_row_list(N): return [i_list() for _ in range(N)]

def prime_factorize(n: int) -> list:
    return_list = []
    while n % 2 == 0:
        return_list.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            return_list.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        return_list.append(n)
    return return_list

q=i_input()
rl=i_row_list(q)
naxnum=0
for r,l in rl:
    maxnum=max(r,l,naxnum)

unums=[]
for i in range(1,maxnum+1):
    if len(prime_factorize(i))==1:
        unums.append(i)


tmprow=[]
cnt=0
for i in range(maxnum+1):
    if i==0 or i==1:
        tmprow.append(cnt)
    else:
        if i in unums and (i+1)/2 in unums:
            cnt+=1
        tmprow.append(cnt)
print(len(tmprow))
for r,l in rl:
    num=tmprow[l]-tmprow[r-1]
    print(num)

Submission status: Runtime Error

Solution code:

url = "https://atcoder.jp//contests/abc134/tasks/abc134_d"

def main():
    n = int(input())
    a = [0]
    a.extend(list(map(int, input().split())))
    balls = [0]*(n+1)
    b = {}
    for i in range(n, 0, -1):
        ball = 0
        for j in range(i, n, i):
            ball += balls[j]
        if ball % 2 != a[i]:
            if ball % 2 >= 2:
                print(-1)
                exit()
            a[i] = 1
            b[i] = 1
    if len(b) == 0:
        print(0)
        exit()
    else:
        print(len(b))
    ks = sorted(b.items(), key=lambda x:x[0])
    for k in ks:
        print(k, end=" ")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


max_ = pow(10, 5)
primes = get_sieve_of_eratosthenes(max_)
num_lile2017 = [0]*max_
primes2 = []
for prime in primes:
    primes2.append(2*prime-1)
like2017 = sorted(list(set(primes2) & set(primes)))
idx = 0
for i in range(max_):
    if (like2017[idx] < i and i < like2017[-1]):
        idx += 1
    num_lile2017[i] += idx

Q = z()
for i in range(Q):
    l, r = zz()
    print(num_lile2017[r+1] - num_lile2017[l])

Submission status: Runtime Error

Solution code:
def prime_num(n):
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            return False
    return True
  
N = int(input())
for _ in range(N):
    nmin, nmax = map(int, input())
    if nmin < 2:
        nmin = 3
    ans = 0
    for i in range(nmin, nmax+1, 2):
        judge1 = prime_num(i)
        if judge1:
            i = (i+1)/2
            judge2 = prime_num(i)
            if judge2:
                ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
ALL = []
cnt = 0
import math
def decide_sosuu(n):
    if n <= 1:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
    return True
for i in range(1,int((10**5)/2)):
    if decide_sosuu(i):
        if decide_sosuu((i*2)-1):
            cnt += 1
            ALL.append(cnt)
        else:
            ALL.append(cnt)
    else:
        ALL.append(cnt)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    if l == 1:
        print(ALL[int(r/2)])
    else:
        print(ALL[int(r/2)] -ALL[int(l/2)-1])

Submission status: Runtime Error

Solution code:
ALL = []
cnt = 0
import math
def decide_sosuu(n):
    if n <= 1:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
    return True
for i in range(1,int((10**5)/2)):
    if decide_sosuu(i):
        if decide_sosuu((i*2)-1):
            cnt += 1
            ALL.append(cnt)
        else:
            ALL.append(cnt)
    else:
        ALL.append(cnt)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(ALL[int(r/2)] -ALL[int(l/2)-1])

Submission status: Runtime Error

Solution code:
def primes(n):
    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
    return [i for i in range(n + 1) if is_prime[i]]

sums = [0,0,0]
curr_sum = 0
ps = primes(10**3)
pset = set(ps)
for i in range(3,10**2+1):
    for p in ps:
        if i%p == 0 and i not in pset:
            break
        if ((i+1)//2)%p == 0 and ((i+1)//2) not in pset:
            break
    else:
        curr_sum += 1
        # print(i)
    sums.append(curr_sum)
    

q = int(input())
ansl = []
for _ in range(q):
    l,r = map(int, input().split())
    ans = sums[r] - sums[l-1]
    ansl.append(ans)

for a in ansl: print(a)

# print(sums[:54])

Submission status: Runtime Error

Solution code:
def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]
        
Q = int(input())
for i in range(Q):
    l, r = input().split()
    l = int(l)
    R = eratosthenes(int(r))
    row = []
    for j in R:
        if j in R and j >= l:
           row.append(j)
    cnt = 0
    for k in row:
      if (k + 1) / 2 in R:
        cnt+=1
    print(cnt)

Submission status: Runtime Error

Solution code:
import math
def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]
        
Q = int(input())
for i in range(Q):
    l, r = input().split()
    l = int(l)
    R = eratosthenes(int(r))
    row = []
    for j in R:
        if j in R and j >= l:
           row.append(j)
    cnt = 0
    for k in row:
    if (k + 1) / 2 in R:
        cnt+=1
    print(cnt)

Submission status: Runtime Error

Solution code:
import math
from itertools import accumulate

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

er_list = eratosthenes(100000)
count = []

j = 0
for i in range(er_list[-1]):
    if i == er_list[j]:
        j += 1
        if (i+1)//2 in er_list:
            count.append(1) 
        else:
            count.append(0)
    else:
        count.append(0)
count = list(accumulate(count))
            
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

Submission status: Runtime Error

Solution code:
import math
from itertools import accumulate

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

er_list = eratosthenes(100000)
count = []

j = 0
for i in range(er_list[-1]):
    if i == er_list[j]:
        j += 1
        if (i+1)//2 in er_list:
            count.append(1) 
        else:
            count.append(0)
            
count = list(accumulate(count))
            
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

Submission status: Runtime Error

Solution code:
import math
def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

ls = eratosthenes(100000)
ls2 = []
count = 0
for i in ls:
    ls2.append(count)
    if (i+1)//2 in ls:
        count += 1
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(ls2[r-1]-ls2[l-1])

Submission status: Runtime Error

Solution code:
import math
def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

ls = eratosthenes(100000)
ls2 = []
count = 0
for i in ls:
    if (i+1)//2 in ls:
        count += 1
    ls2.append(count)

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

Submission status: Runtime Error

Solution code:
def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

ls = eratosthenes(100000)
ls2 = []
count = 0
for i in ls:
    if (i+1)//2 in ls:
        count += 1
    ls2.append(count)

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

Submission status: Runtime Error

Solution code:
def prime_eratosthenes(n):
    prime_list = []
    num_list=[]
    for i in range(2, n+1):
        if i not in num_list:
            prime_list.append(i)
            for j in range(i*i, n+1, i):
                num_list.append(j)
    return prime_list

ls = prime_eratosthenes(10000)
ls2 = [i+1 for i in range(10000)]
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    ans = 0
    for j in range(l-1, r):
        if (ls2[j] in ls) and (ls2[j+1]//2 in ls):
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import math

def is_prime(x):
  if x == 1:
    return False
  elif x == 2:
    return True
  else:
    for i in range(3, math.sqrt(x)//1+1):
      if x%i == 0:
        return False
    return True

print(is_prime(3))

Submission status: Runtime Error

Solution code:
Q = int(input())

ls = [list(map(int,input().split())) for i in range(Q)]
n_max = max(ls)[1]

prime = []
data = [i for i in range(2,n_max+1)]
limit = n_max**(1/2)
while True:
    p = data[0]
    if limit<=p:
        break
    prime.append(p)
    data = [i for i in data if i%p!=0]
prime = prime +data

ans_ls = [0]*(1+n_max)
for i in range(1,n_max+1):
    if i in prime:
        if (i+1)//2 in prime:
            ans_ls[i] =ans_ls[i-1] + 1
        else:
            ans_ls[i] = ans_ls[i-1]
    else:
        ans_ls[i] = ans_ls[i - 1]

for l,r in ls:
    print(ans_ls[r]-ans_ls[l-1])

Submission status: Runtime Error

Solution code:
def eratosthenes(n):
    is_prime = [True for i in range(n+1)]
    is_prime[0], is_prime[1] = False, False
    prime = []
    for i in range(2, n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(2*i, n+1, i):
                is_prime[j] = False
    return prime
    

Q = int(input())
N = 10**5

prime = eratosthenes(N)
prime_num = [0 for i in range(N+1)]
for p in prime:
    prime_num[p] = 1
    
count = 0
ans = [0 for i in range(N+1)]
for i in range(1, N+1, 2):
    if prime_num[i] == 1 and prime_num[(i+1)//2] == 1:
        count += 1
    ans[i] = count
    
for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r+2] - ans[l-2])

Submission status: Runtime Error

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
def is_prime(n):
    if n == 1: return False

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

    return True
n = int(input())
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
b[c:] = add 
b[0::2] = 0

for i in range(n):
    l, r =map(int,input().split())
    print(b[max(0, l[i] - 2)] - b[r[i]])

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

mini = min(min(l), min(r))
maxi = max(max(l), max(r))
ans = [0] * (maxi + 1)
prime = [0] * (maxi + 1)
def judge_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    
    return True if n != 1 else False

for i in range((mini + 1) // 2, maxi + 1):
    prime[i] = judge_prime(i)

for i in range(mini, maxi + 1, 2):
    ans[i] = ans[i - 2] + 1 if prime[i] and prime[(i + 1) // 2] else ans[i - 2
for i in range(q):
    print(ans[r[i]] - ans[max(0, l[i] - 2)])

Submission status: Runtime Error

Solution code:
B = [False]*10005
C = [0]*10005
for i in range(2,10001):
    if not B[i]:
      	for j in range(i+i,10001,i):
          	B[j]=True
for i in range(3,10001,2):
    if not B[i] and not B[(i+1)//2]:
        C[i]+=1
for i in range(3,10001):
    C[i]=C[i]+C[i-1]
    
N = int(input())
for _ in range(N):
    a, b = map(int,input().split())
    print(C[b]-C[a])

Submission status: Runtime Error

Solution code:
B = [False]*10005
C = [0]*10005
for i in range(2,10001):
    if not B[i]:
      	for j in range(i+i,10001,i):
          	B[j]=True
for i in range(3,10001,2):
    if not B[i] and not B[(i+1)//2]:
        C[i]+=1
for i in range(3,10001):
    C[i]=C[i]+C[i-1]
    
N = int(input())
for _ in range(N):
    a, b = map(int,input().split())
    print(C[b]-C[a-1])

Submission status: Runtime Error

Solution code:
B = [False]*10010
C = [0]*10010
for i in range(2,10005):
    if not B[i]:
        j = i+i
        while j < 10005:
            B[j]= True
            j+=i
for i in range(3,10005,2):
    if not B[i] and not B[(i+1)//2]:
        C[i]+=1
for i in range(3,10005):
    C[i]=C[i]+C[i-1]
    
N = int(input())
for _ in range(N):
    a, b = map(int,input().split())
    print(C[b]-C[a-1])

Submission status: Runtime Error

Solution code:
B = [False]*10010
C = [0]*10010
for i in range(2,10005):
    if not B[i]:
        j = i+i
        while j < 10005:
            B[j]= True
            j+=i
for i in range(3,10005,2):
    if not B[i] and not int(B[(i+1)/2]):
        C[i]+=1
for i in range(3,10005):
    C[i]=C[i]+C[i-1]
    
N = int(input())
for _ in range(N):
    a, b = map(int,input().split())
    print(C[b]-C[a-1])

Submission status: Runtime Error

Solution code:
B = [False]*10010
C = [0]*10010
for i in range(2,10005):
    if !B[i]:
        j = i+i
        while j < 10005:
            B[j]= True
            j+=i
for i in range(3,10005,2):
    if !B[i] and !B[(i+1)//2]:
        C[i]+=1
for i in range(3,10005):
    C[i]=C[i]+C[i-1]
    
N = int(input())
for _ in range(N):
    a, b = map(int,input().split())
    print(c[b]-c[a-1])

Submission status: Runtime Error

Solution code:
data = sorted(list(range(10**5+1)))
prime_bool = [True]*(10**5+1)
prime_bool[0] = False
 
for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    k = 2
    while k*p <= max(a):
      prime_bool[k*p] = False
      k += 1

count_list = [0]*(10**5+1)
for i in range(1, 10**5+1):
  count_list[i] = count_list[i-1]
  if prime_bool[i] and prime_bool[(i+1)//2]:
    count_list[i] += 1

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

Submission status: Runtime Error

Solution code:
#ABC 084 D - 2017 Like Number
from itertools import accumulate

def isPrime(x):
    if x == 2: flag = True
    else:
        flag = True
        if x % 2 == 0:
            flag = False
        
        i = 3
        while i**2 <= x and flag == True:
            if x % i == 0:
                flag = False
            else:
                i += 2
    return True if flag == True else False

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

max_arr = max(arr)[1]
res_arr = [0]*(max_arr+1)
for i in range(3,max_arr+1,2):
    v1, v2 = i, (i+1)//2
    if isPrime(v1) == True and isPrime(v2) == True:
        res_arr[i] = 1

cumsum = list(accumulate(res_arr))
#print(res_arr)
#print(cumsum)
for i in range(q):
    l,r = arr[i][0], arr[i][1]
    print(cumsum[r] - cumsum[l-1])

Submission status: Runtime Error

Solution code:
def era(M):
    p = [1] * M
    p[0] = p[1] = 0
    for x in range(2, int(~-M**.5) + 1):
        if p[x]:
            for y in range(x*x, M, x):
                p[y] = 0
    return p
INF = 10**5 + 1
E = erat(INF)
Q = [0] * INF
from itertools import*
for i in range(INF):
    q[i] = i%2 * p[i] * p[-~i//2]
*a, = accumulate([0] + q)
for _ in [None] * int(input()):
    l, r = map(int, input().split())
    print(a[-~r] - a[l])

Submission status: Runtime Error

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

similar=[]
cnt=0
for i in range(10**5+2):
    if i<=2:
        similar.append(0)
    else:
        if is_prime(i)==True and (is_prime((i+1)/2))==True:
            cnt+=1
        similar.append(cnt)

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

Submission status: Runtime Error

Solution code:
a=[3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541, 613, 661, 673, 733, 757, 877, 997, 1093, 1153, 1201, 1213, 1237, 1321, 1381, 1453, 1621, 1657, 1753, 1873, 1933, 1993, 2017]
A=[]
B=[]
c=0
ans=0
for i in range(2017):
    if i in a:
        c+=1
    B.append(c)
    
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    A.append(B[r]-B[l]+1)
for i in range (q):
    print(A[i])

Submission status: Runtime Error

Solution code:
a=[3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541, 613, 661, 673, 733, 757, 877, 997, 1093, 1153, 1201, 1213, 1237, 1321, 1381, 1453, 1621, 1657, 1753, 1873, 1933, 1993, 2017]
A=[]
B=[]
c=0
ans=0
for i in range(2017):
    if i in a:
        c+=1
    B.append(c)
    
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    A.append(B[r]-B[l])
for i in range (q):
    print(A[i])

Submission status: Runtime Error

Solution code:
a=[3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541, 613, 661, 673, 733, 757, 877, 997, 1093, 1153, 1201, 1213, 1237, 1321, 1381, 1453, 1621, 1657, 1753, 1873, 1933, 1993, 2017]
for i in (sosuu):
    if (i+1)/2 in sosuu:
        a.append(i)
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        if j in (a):
            ans+=1
    print(ans)
    ans=0

Submission status: Runtime Error

Solution code:
import math

Q = int(input())

def prime(n):
	if n > 1:
		for i in range(2,math.floor(math.sqrt(n))+1):
			if (n % i) == 0:
				return(False)
				break
		else:
			return(True)
	else:
		return(False)

Numero = [0]*10001
for i in range (0, 10001):
	if prime(i) == 1 and prime(int((i+1)/2)) == 1:
		Numero[i]+=1
	else:
		continue

Umero = []

for i in range (0, 10001):
	Umero.append(sum(Numero[0:i]))

for i in range (0, Q):
	A, B = map(int, input().split())
	print(Umero[B+1]-Umero[A])