Problem:


Score : 400 points

Problem Statement

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

You are given Q queries.

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

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

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

Sample Input 1

1
3 7

Sample Output 1

2

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

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

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

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

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

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

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:

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
                
    if not found:
        prime.append(i)

# print(prime)


q = int(input())

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

        xi = bisect.bisect_right(prime, i)
        #print(xi)

        if prime[xi-1] != i:
            continue

        i2 = (i+1)//2
        yi = bisect.bisect_right(prime, i2, hi = xi)
        if prime[yi-1] != i2:
            continue

        ans += 1

    print(ans)

Submission status: Time Limit Exceeded

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
                
    if not found:
        prime.append(i)

# print(prime)


q = int(input())

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

        #si = bisect.bisect_left(prime,i)
        xi = bisect.bisect_right(prime, i)
        yi = bisect.bisect_right(prime, (i+1)//2)
        ans += 1 if prime[xi-1] == i and prime[yi-1] == (i+1)//2 else 0

    print(ans)

Submission status: Time Limit Exceeded

Solution code:

import math
import bisect


prime = [2,3,5,7]
for i in range(11,100000):

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

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

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

#print(prime)


q = int(input())
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):

        #si = bisect.bisect_left(prime,i)
        xi = bisect.bisect_right(prime, i)
        yi = bisect.bisect_right(prime, (i+1)//2)
        ans += 1 if prime[xi-1] == i and prime[yi-1] == (i+1)//2 else 0

    print(ans)

Submission status: Time Limit Exceeded

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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
number = np.arange(10**5+1)
primes = np.ones(10**5+1)

for i in range(10**3):
  if i <= 1:
    primes[i] = 0
    continue
  if primes[i] == 1:
    primes[number%i==0]=0
    primes[i] = 1
    
N = int(input())
for i in range(N):
  s, e = list(map(int, input().split()))
  res = 0
  for j in range(s, e+1):
    if primes[j] == 1 and primes[int((j+1)/2)]:
      res += 1
  print(res)

Submission status: Time Limit Exceeded

Solution code:
L=[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())
L2=[]
for _ in range(Q):
  l,r=map(int,input().split())
  i=0
  li=0
  f1=f2=0
  for x in L:
    if f1==0 and l<=x:
      f1=1
      li=i
    if f2==0 and r<x:
      f2=1
      ri=i
    i+=1
  if f2==0:
    ri=672
  L2.append(ri-li)
for x in L2:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
n=10**5+2
#n=100
p=[0]*n
ac=[0]*n
def prime_list(x):
    for i in range(2,x+1):
        flg=True
        for j in range(2,int(i**0.5)+1):
            if i%j==0:
                flg=False
        if flg==True:
            p[i]=1

def elato(x):
    pr=list(range(2,x+1))
    for i in pr:
        for j in pr:
            if j!=i and j%i==0:
                pr.remove(j)
    return pr
            
for i in elato(n):
    p[i]=1
#print(p)
pre=0
for i in range(n):
    if p[i]==1 and p[int((i+1)/2)]==1 and i%2==1:
        k=1
    else:
        k=0
    pre+=k
    ac[i]=pre

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

Submission status: Time Limit Exceeded

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

N = 10 ** 5
pn = sieve(N + 1)

dp = [0] * (N + 1)
for i in pn:
    if (i + 1) // 2 in pn:
        dp[i] += 1
        
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(sum(dp[l : r + 1]))

Submission status: Time Limit Exceeded

Solution code:
import math
N = 10**5

Q = int(input())


def eratosthenes(n):
    """n以下の素数をエラトステネスの篩によって求める."""
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


primes = eratosthenes(N)

like_2017 = [False] * (10**5 + 1)

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


c = 0
C = [0]
for i in range(1, 10**5 + 1):
    if like_2017[i]:
        c += 1
    C.append(c)


for _ in range(Q):
    left, right = map(int, input().split())
    print(C[right] - C[left - 1])

Submission status: Time Limit Exceeded

Solution code:
import math
N = 10**5

Q = int(input())


def eratosthenes(n):
    """n以下の素数をエラトステネスの篩によって求める."""
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


primes = eratosthenes(N)

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


c = 0
C = [0]
for i in range(1, 10**5 + 1):
    if i in like_2017:
        c += 1
    C.append(c)


for _ in range(Q):
    left, right = map(int, input().split())
    print(C[right] - C[left - 1])

Submission status: Time Limit Exceeded

Solution code:
prime=[]
n=10**5
is_prime=True
for i in range(2,n+1):
    is_prime=True
    for p in prime:
        if i%p==0:
            is_prime=False
            break
    if is_prime:
        prime.append(i)
q=int(input())
query=[[int(i) for i in input().split()] for j in range(q)]
for qu in query:
    cnt=0
    for j in range(qu[0], qu[1]+1, 2):
        if (j in prime) and (((j+1)//2) in prime):
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

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

BIT = Bit(10**5+1)

plist = primes(10**5+1)
# print(plist)
pp = []
for p in plist[1:]:
    if (p+1) //2 in plist:
        pp.append( p )
        BIT.add(p,1)
# print(pp)

Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    if l in pp:
        l-=1
    if r in pp:
        r+=1
    print( BIT.sum(r) - BIT.sum(l) )

Submission status: Time Limit Exceeded

Solution code:
elst = [True for _ in range(10**5+1)]
elst[0] = False

for i, e in enumerate(elst):
  if e:
    for j in range(2*i+1, 10**5+1, i+1):
      elst[j] = False

q = int(input())
for _ in range(q):
  l, r = map(int, input().split())
  l = l if l % 2 == 1 else l + 1
  r = r if r % 2 == 0 else r + 1
  c = 0
  for x in range(l, r, 2):
    if elst[x-1] and elst[(x + 1) // 2 - 1]:
      c += 1
  print(c)

Submission status: Time Limit Exceeded

Solution code:
# D
prime_num = set([2])
size = int(1e5)*2+1
for i in range(3,size,2):
    for p in prime_num:
        if i%p==0: break
        else: continue
    else:
        prime_num.add(i)

cnt = [0]*(int(1e5)+2)
for p in prime_num:
    if p<=int(1e5) and (p+1)//2 in prime_num:
        cnt[p] = 1
for i in range(1, int(1e5)+2):
    cnt[i] += cnt[i-1]
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l])

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]
prime = [True for _ in range(10**5 + 10)]
prime[0] = prime[1] = False
for i in range(2, 320):
    if prime[i]:
        for j in range(i * 2, 10 ** 5 + 10, i):
            prime[j] = False
for q in query:
    ans = 0
    l, r = q
    for i in range(l, r + 1, 2):
        if prime[i] and prime[(i + 1) // 2]:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

result = []

def prime_number(n):
    for i in range(2, n+1):
        if i * i > n:
            return True
        if n%i == 0:
            return False
    return n != 1

for i in range(N):
    res = 0
    for j in range(L[i][0], L[i][1]+1):
        if prime_number(j) and prime_number((j+1)//2):
            res += 1
    result.append(res)

for res in result:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import math
Q = int(input())
ary = list(list(map(int, input().split())) for _ in range(Q)) 
pary = []
for r in ary:
    a = r[0]
    b = r[1]
    cnt = 0
    prime = []
    limit = math.sqrt(b)
    # 2~nまでの配列を生成
    data = [i + 1 for i in range(1, b)]
    
    while not limit <= data[0]:        
        prime.append(data[0])
        data = [e for e in data if e % data[0] != 0]    
    pri_ary = prime+data # a-b間の素数配列
    
    for i in range(a, b+1):
        if i % 2 == 0:
            continue
        if i in pri_ary and (i+1)//2 in pri_ary:
            cnt += 1
    pary.append(cnt)
for i in pary:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import math
Q = int(input())
ary = list(list(map(int, input().split())) for _ in range(Q)) 

# エラトステネス
def eratosthenes(n):
  if not isinstance(n, int):
    raise TypeError('n is int type.')
  if n < 2:
    raise ValueError('n is more than 2')

  prime = []
  limit = math.sqrt(n)
  # 2~nまでの配列を生成
  data = [i + 1 for i in range(1, n)]
  
  while True:
    p = data[0]
    if limit <= p:
      return prime + data
    prime.append(p)
    data = [e for e in data if e % p != 0]    

ary2 =[]
for a in ary:
    cnt = 0
    primary_ary = eratosthenes(a[1])
    for i in range(a[0], a[1]+1):
        if i % 2 == 0:
            continue
        if i in primary_ary and (i+1)//2 in primary_ary:
            cnt += 1
    ary2.append(cnt)
for a in ary2:
    print(a)

Submission status: Time Limit Exceeded

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

def is_primary(n):
    if n < 2:
        return False
    for i in range(2,n//2+1):
        if n % i == 0:
            return False
    return True

ary2=[]
for n in ary:
    cnt = 0
    for i in range(n[0],n[1]+1):
        if not i % 2 == 1:
            continue
        if is_primary(i) and is_primary((i+1)//2):
            cnt += 1
    ary2.append(cnt)
for n in ary2:
    print(n)

Submission status: Time Limit Exceeded

Solution code:
# https://abc084.contest.atcoder.jp/tasks/abc084_d


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


def main():
    p_l = primes(10**5)
    total = [0 for _ in range(10 ** 5 + 1)]
    for i in range(3, 10 ** 5 + 1, 2):
        if i in p_l and (i + 1) // 2 in p_l:
            total[i] = 1
    for i in range(3, 10 ** 5 + 1):
        total[i] += total[i - 1]

    # print(total[:10])
    Q = int(input())
    lrs = [list(map(int, input().split())) for _ in range(Q)]
    for lr in lrs:
        print(total[lr[1]] - total[lr[0]-1])


main()

Submission status: Time Limit Exceeded

Solution code:
# https://abc084.contest.atcoder.jp/tasks/abc084_d

def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False

    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1

    return True


def main():
    Q = int(input())
    lrs = [list(map(int, input().split())) for _ in range(Q)]
    p_l = [i for i in range(2, 10**5 + 1) if is_prime(i)]

    for lr in lrs:
        ans = 0
        for i in range(lr[0], lr[1] + 1, 2):
            ans += 1 if i in p_l and (i + 1) // 2 in p_l else 0
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import math
q=int(input())
a=[]
n=10**5
for i in range(q):
    start,end=map(int,input().split())
    a.append(list(range(start,end+1,2)))

def sieve_of_eratosthenes(n):
    prime=[]
    limit=math.sqrt(n)
    data=[i+1 for i in range(1,n)]
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]

prime_data=sieve_of_eratosthenes(n)
for i in range(q):
    ans=0
    for j in range(len(a[i])):
        if a[i][j] in prime_data and (a[i][j]+1)//2 in prime_data:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
        sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

q = int(input())
pl = primes(10**5)
ql = [p*2-1 for p in pl if p*2-1 in pl and p*2-1<=10**5+1]
for _ in range(q):
  l,r = map(int,input().split())
  fil = list(filter(lambda x: l<=x<=r, ql))
  print(len(fil))

Submission status: Time Limit Exceeded

Solution code:
def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
        sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

q = int(input())
pl = primes(10**5)
ql = [p*2-1 for p in pl if p*2-1 in pl and p*2-1<=10**5+1]
for _ in range(q):
  l,r = map(int,input().split())
  fil = list(filter(lambda x: l<=x<=r, ql))
  print(len(fil))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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(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


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

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 isPrime(n):
    if n == 0 or n == 1:
        return False
    for i in range(2, n):  # 第二引数は sqrt(num)+1 でも良い
        if n % i == 0:
            return False

    return True


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

Solution code:
import math

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def isPrime(i):
    if i < 2:
        return False
    elif i == 2:
        return True
    elif i % 2 == 0:
        return False
    for j in range(3, int(i**0.5)+1, 2):
        if i % j == 0:
            return False
    return True


class RSQ_segment_tree:
    """Range Sum Query
    0 indexed
    """

    def __init__(self, init_num, n):
        # represent tree as array
        # parent of k : (k - 1) // 2
        # children of k : 2 * k + 1 and 2 * k + 2
        self.ex = 0
        while(2 ** self.ex < n):
            self.ex += 1
        self.bottom = 2 ** self.ex - 1
        self.tree = [init_num for _ in range(2 ** (self.ex + 1) - 1)]

    def __str__(self):
        tmp = "tree structure\n"
        tree = str(self.tree)
        return tmp + tree + "\n"

    def min_update(self, position, new):
        # chi : child
        # par : parent
        chi = self.bottom + position
        self.tree[chi] = new
        for _ in range(self.ex):
            par = (chi - 1) // 2
            ano_chi = [chi + 1, chi - 1][chi % 2 == 0]
            self.tree[par] = min(self.tree[chi], self.tree[ano_chi])
            chi = par
        return True
    
    def sum_find(self, left, right, first=False):
        """[left, right]"""
        if first is True:    
            left = self.bottom + left
            right = self.bottom + right
        if left == right:
            return self.tree[left]

        ret = 0
        while left < right:
            if left % 2 == 1:
                pass
            else:
                ret -= self.tree[left-1]
                left -= 1

            if right % 2 == 1:
                ret += self.tree[right]
                right -= 1
            # print(left, right)
            left = (left-1)//2
            right = (right-1)//2
        return ret + self.tree[left]
    
    def make_sum(self):
        for i in reversed(range(self.bottom)):
            self.tree[i] = self.tree[(i+1)*2] + self.tree[(i+1)*2-1]


def inpl(): return list(map(int, input().split()))

Q = int(input())
# query = [inpl() for i in range(Q)]
N = 10 ** 5

rsq = RSQ_segment_tree(0, N)
prime = [False] * (N+1)
for i in range(2, N+1):
    prime[i] = isPrime(i)
    rsq.tree[i+rsq.bottom] = int(prime[i] and prime[(i+1)//2])

rsq.make_sum()
# print(rsq.tree[rsq.bottom:rsq.bottom+10])
for _ in range(Q):
    l, r = inpl()
    print(rsq.sum_find(l, r, first=True))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def isPrime(i):
    if i == 2 or i == 3:
        return True
    elif i % 2 == 0:
        return False
    p = 3
    tmp = i ** 0.5
    while i != 1:
        if i % p == 0:
            return False
        elif p > tmp:
            return True
        else:
            p += 2
    return True


class RSQ_segment_tree:
    """Range Sum Query
    0 indexed
    """

    def __init__(self, init_num, n):
        # represent tree as array
        # parent of k : (k - 1) // 2
        # children of k : 2 * k + 1 and 2 * k + 2
        self.ex = 0
        while(2 ** self.ex < n):
            self.ex += 1
        self.bottom = 2 ** self.ex - 1
        self.tree = [init_num for _ in range(2 ** (self.ex + 1) - 1)]

    def __str__(self):
        tmp = "tree structure\n"
        tree = str(self.tree)
        return tmp + tree + "\n"

    def min_update(self, position, new):
        # chi : child
        # par : parent
        chi = self.bottom + position
        self.tree[chi] = new
        for _ in range(self.ex):
            par = (chi - 1) // 2
            ano_chi = [chi + 1, chi - 1][chi % 2 == 0]
            self.tree[par] = min(self.tree[chi], self.tree[ano_chi])
            chi = par
        return True
    
    def sum_find(self, left, right, first=False):
        """[left, right]"""
        if first is True:    
            left = self.bottom + left
            right = self.bottom + right
        if left == right:
            return self.tree[left]

        ret = 0
        while left < right:
            if left % 2 == 1:
                pass
            else:
                ret -= self.tree[left-1]
                left -= 1

            if right % 2 == 1:
                ret += self.tree[right]
                right -= 1
            # print(left, right)
            left = (left-1)//2
            right = (right-1)//2
        return ret + self.tree[left]
    
    def make_sum(self):
        for i in reversed(range(self.bottom)):
            self.tree[i] = self.tree[(i+1)*2] + self.tree[(i+1)*2-1]


def inpl(): return list(map(int, input().split()))

Q = int(input())
# query = [inpl() for i in range(Q)]
N = 10 ** 5

rsq = RSQ_segment_tree(0, N)
prime = [False] * (N+1)
for i in range(2, N+1):
    prime[i] = isPrime(i)
    rsq.tree[i+rsq.bottom] = int(prime[i] and prime[(i+1)//2])

rsq.make_sum()
# print(rsq.tree[rsq.bottom:rsq.bottom+10])
for _ in range(Q):
    l, r = inpl()
    print(rsq.sum_find(l, r, first=True))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def isPrime(i):
    if i == 2 or i == 3:
        return True
    elif i % 2 == 0:
        return False
    p = 3
    tmp = i ** 0.5
    while i != 1:
        if i % p == 0:
            return False
        elif p > tmp:
            return True
        else:
            p += 2
    return True


class RSQ_segment_tree:
    """Range Sum Query
    0 indexed
    """

    def __init__(self, init_num, n):
        # represent tree as array
        # parent of k : (k - 1) // 2
        # children of k : 2 * k + 1 and 2 * k + 2
        self.ex = 0
        while(2 ** self.ex < n):
            self.ex += 1
        self.bottom = 2 ** self.ex - 1
        self.tree = [init_num for _ in range(2 ** (self.ex + 1) - 1)]

    def __str__(self):
        tmp = "tree structure\n"
        tree = str(self.tree)
        return tmp + tree + "\n"

    def min_update(self, position, new):
        # chi : child
        # par : parent
        chi = self.bottom + position
        self.tree[chi] = new
        for _ in range(self.ex):
            par = (chi - 1) // 2
            ano_chi = [chi + 1, chi - 1][chi % 2 == 0]
            self.tree[par] = min(self.tree[chi], self.tree[ano_chi])
            chi = par
        return True
    
    def sum_find(self, left, right, first=False):
        """[left, right]"""
        if first is True:    
            left = self.bottom + left
            right = self.bottom + right
        if left == right:
            return self.tree[left]

        if left % 2 == 1:
            tmpl = 0
        else:
            tmpl = -1 * self.tree[left-1]
            left -= 1

        if right % 2 == 1:
            tmpr = self.tree[right]
            right -= 1
        else:
            tmpr = 0
        # print(left, right)
        return tmpl + tmpr + self.sum_find((left-1)//2, (right-1)//2)
    
    def make_sum(self):
        for i in reversed(range(self.bottom)):
            self.tree[i] = self.tree[(i+1)*2] + self.tree[(i+1)*2-1]


def inpl(): return list(map(int, input().split()))

Q = int(input())
# query = [inpl() for i in range(Q)]
N = 10 ** 5

rsq = RSQ_segment_tree(0, N)
prime = [False] * (N+1)
for i in range(2, N+1):
    prime[i] = isPrime(i)
    rsq.tree[i+rsq.bottom] = int(prime[i] and prime[(i+1)//2])

rsq.make_sum()
# print(rsq.tree[rsq.bottom:rsq.bottom+10])
for _ in range(Q):
    l, r = inpl()
    print(rsq.sum_find(l, r, first=True))