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:
q = int(input())
kueri =[]
for _ in range(q):
    l,r =map(int,input().split())
    kueri.append((l,r))

n = 10**5
d=[]
import numpy as np 
def judge(p):
    if p == 1:
        return 0
    m = (p+1)//2
    return Prime(p)*Prime(m)

def Prime(k):
    if k in  [1,4,6]:
        return 0
    elif k in [2,3,5]:
        return 1
    elif k %6 == 1 or 5:
        for i in range(2,int(np.sqrt(k)+1)):
            if k % i == 0:
                return 0
        return 1
    else:
        return 0
for k in range(1,n+1):
    if k%2 == 0:
        d.append(0)
    else:
        d.append(judge(k))

for l,r in kueri:
    print(sum(d[l-1:r]))

Submission status: Time Limit Exceeded

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

n = 10**5
d=[]
import numpy as np 
def judge(p):
    if p == 1:
        return 0
    for i in range(2,int(np.sqrt(p))+1):
        if p %i == 0:
            return 0
    m = (p+1)//2
    for i in range(2,int(np.sqrt(m)+1)):
        if m%i == 0:
            return 0
    return 1



for k in range(1,n+1):
    if k%2 == 0:
        d.append(0)
    else:
        d.append(judge(k))

for l,r in kueri:
    print(sum(d[l-1:r]))

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())#これはTLE
num = [0]*(100000+1)
num[2] = 2
for i in range(3,100000+1,2):
    if num[i] != 0:
        continue
    if num[i] == 0:
        num[i] = 2
        for j in range(i+1,100000+1):
            if num[j] == 1:
                continue
            if j % i == 0:
                num[j] = 1

like2017 = [0]*(100000+1)
for i in range(3,100000+1):
    if num[i] == 2:
        if num[(i+1)//2] == 2:
            like2017[i] = 1

ruiseki_wa = [0]*(100000+1)
for i in range(100000):
    ruiseki_wa[i+1] = ruiseki_wa[i] + like2017[i]


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

Submission status: Time Limit Exceeded

Solution code:
import math

q = int(input())
cnt = [0] * (5 * 10 ** 4)
cnt[1] = 1
cnt[2] = 2


def is_prime(n):
    visit = []
    if n % 2 == 0:
        return 0
    for i in range(3, 1 + math.ceil(n ** (0.5))):
        if i not in visit:
            if n % i == 0:
                return 0
            else:
                visit.append(i)
    return 1


for i in range(3, 5 * 10 ** 4):
    odd = 2 * i + 1
    if odd % 3 != 1:
        cnt[i] = cnt[i - 1]
    else:
        k = 0
        if is_prime(odd) and is_prime((odd + 1) // 2):
            k = 1
            # print(odd, is_prime(odd), is_prime((odd + 1) // 2))
        cnt[i] = cnt[i - 1] + k
cnt.append(0)
for i in range(q):
    l, r = map(int, input().split())
    print(cnt[(r - 1) // 2] - cnt[(l - 3) // 2])

Submission status: Time Limit Exceeded

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

primes = [2]
likes_nums = []


def is_prime(num):
    # 今まででた素数で割っていくと、自身が素数かどうかわかる
    if num == 1:
        return False
    if primes[-1] <= math.ceil(math.sqrt(num)):
        for i in range(primes[-1], math.ceil(math.sqrt(num)) + 1):
            is_prime = True
            # 今まででた素数で割っていくと、自身が素数かどうかわかる
            for p in primes:
                if i % p == 0:
                    is_prime = False
            if is_prime:
                primes.append(i)
    for p in primes:
        # 全てprimesを見るのは時間が勿体無いので、自身よりも大きいもの・もしくは同じになったら抜ける.
        # もし素数でないのであれば、p<nの間にあるはず。ない状態で、同じ数値まで来た場合も素数
        if num <= p:
            return True

        if num % p == 0:
            return False
    return True


def check(num):
    if num in likes_nums:
        return True
    if is_prime(num) and is_prime((num + 1) / 2):
        likes_nums.append(num)
        return True
    else:
        return False


for start, end in num_ranges:
    count = 0
    for i in range(start, end + 1):
        if i % 2 == 0:
            continue
        if check(i):
            # print(i)
            count += 1
    print(count)

Submission status: Time Limit Exceeded

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

primes = [2]


def is_prime(num):
    # 今まででた素数で割っていくと、自身が素数かどうかわかる
    if num == 1:
        return False
    if primes[-1] <= math.ceil(math.sqrt(num)):
        for i in range(primes[-1], math.ceil(math.sqrt(num)) + 1):
            is_prime = True
            # 今まででた素数で割っていくと、自身が素数かどうかわかる
            for p in primes:
                if i % p == 0:
                    is_prime = False
            if is_prime:
                primes.append(i)
    for p in primes:
        # 全てprimesを見るのは時間が勿体無いので、自身よりも大きいもの・もしくは同じになったら抜ける.
        # もし素数でないのであれば、p<nの間にあるはず。ない状態で、同じ数値まで来た場合も素数
        if num <= p:
            return True
        if num % p == 0:
            return False
    return True


def check(num):
    if is_prime(num) and is_prime((num + 1) / 2):
        return True
    else:
        return False


for start, end in num_ranges:
    count = 0
    for i in range(start, end + 1):
        if i % 2 == 0:
            continue
        if check(i):
            # print(i)
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#　n以下の整数の素数列挙（エラトステネスの篩）
#-------------------------------------------------------------------------
import numpy as np

def eth(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
#-------------------------------------------------------------------------
import itertools
import sys
input = sys.stdin.buffer.readline

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

q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
def get_prime(x):
    if x <= 1:
        return []
    prime = [2]
    limit = int(x**0.5)
    
    data = [i + 1 for i in range(2, x, 2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j%data[0] != 0]
    
    return prime + data
    

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

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt


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


Q = int(input())

for i in range(Q):
    l, r = map(int, input().split())
    count = 0
    for j in range(l, r+1, 2):
        count += is_prime(j) * is_prime((j+1)//2)
    print(count)

Submission status: Time Limit Exceeded

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 is_prime

is_prime = primes(10**5)

Q = int(input())

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

    cnt = 0
    for j in range(l, r+1):
        if is_prime[j] and is_prime[(j+1)//2]:
            cnt += 1
    ans.append(cnt)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(n**(1/2)) + 1):
        if n % k == 0:
            return False

    return True

Q = int(input())

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

    cnt = 0
    for j in range(l, r+1):
        if is_prime(j) and is_prime((j+1)//2):
            cnt += 1
    ans.append(cnt)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
Start = []
End = []
for _ in range(Q):
    l, r = map(int, input().split())
    Start.append(l)
    End.append(r)

e = max(End)


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


def like_primes(n):
    A = [0]* (e+1)
    for i in n:
        if (i + 1) // 2 in n:
            A[i] = 1
    return A


A = like_primes(primes(e))
for i in range(Q):
    print(A[Start[i]:End[i]+1].count(1))

Submission status: Time Limit Exceeded

Solution code:
import sys 
import bisect
import numpy as np

input = sys.stdin.readline

def get_prime_numbers(n):
    """
    This returns ndarray of prime numbers each within [2, n].
    n >= 3 is required.
    """
    primes = np.concatenate( (np.array([2]), np.arange(3, n+1, 2)) )
    index = 1
    while index < len(primes):
        primes = np.concatenate( (primes[:index+1], primes[index+1:][primes[index+1:] % primes[index] != 0]) )
        index += 1
    return primes

primes = get_prime_numbers(100000)
numbers_like_2017 = []
for prime in primes[1:]:
    t = (prime + 1) // 2
    if t == primes[bisect.bisect_left(primes, t)]:  #if t in primes
        numbers_like_2017.append(prime)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(numbers_like_2017, r) - bisect.bisect_left(numbers_like_2017, l))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
Q = int(input())
LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

@lru_cache(maxsize=None)
def isprime(x):
    if x == 1:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

like = [False] * (10 ** 5 + 1)
for x in range(1, len(like), 2):
    like[x] = isprime(x) and isprime((x + 1) // 2)

for l, r in LR:
    ans = len([1 for x in like[l:r+1] if x])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def sieve_of_eratosthenes_2017(N):
    numbers = [n & 1 for n in range(N + 1)]
    numbers[1] = 0
    numbers[2] = 1
    like2017 = []
    p = 1
    while True:
        while not numbers[p]:
            p += 2
        if numbers[(p + 1) >> 1]:
            like2017.append(p)
        if p * p > N:
            for i in range(p, N + 1, 2):
                if (i + 1) >> 1:
                    like2017.append(i)
            return like2017
        for i in range(p * 2, N + 1, p):
            numbers[i] = 0
        p += 2

like2017 = np.array(sieve_of_eratosthenes_2017(10 ** 5), dtype=np.int32)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    lindex = np.searchsorted(like2017, l)
    rindex = np.searchsorted(like2017, r, side="right")
    print(rindex - lindex)

Submission status: Time Limit Exceeded

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

d = [0]*(10**5+1)
for i in range(len(l)-1):
    for j in range(i, len(l)):
        if l[i] == (l[j]+1)//2: d[l[j]] += 1
for i in range(1, 10**5+1): d[i] += d[i-1]
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(d[r]-d[l-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def isprime(x):
    if x == 1:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

Q = int(input())
for _ in range(Q):
    l, r = map(int, sys.stdin.readline().split())
    ans = 0
    for x in range(l, r + 1, 2):
        if isprime(x) and isprime((x + 1) // 2):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):  
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors
def islike2017(i):
  if i%2==0:
    return False
  if len(make_divisors(i))==2:
    if len(make_divisors(((i+1)//2)))==2:
      return True
  return False
def main():
  q=int(input())
  lr=[list(map(int,input().split())) for _ in range(q)]
  all=[lri[0] for lri in lr]
  all[q:q]=[lri[1] for lri in lr]
  all.sort()
  d={}
  c=0
  d[all[0]]=c
  for i in range(2*q-1):
    for j in range(all[i],all[i+1]):
      if islike2017(j):
        c+=1
    d[all[i+1]]=c
  for l,r in lr:
    a=d[r]-d[l]
    a+=1 if islike2017(r) else 0
    print(a)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
memo = [0]*(10**5+1)
def eratos2():
    primes = []
    for i in range(2, 10**4):
        flag = True
        for p in primes:
            if i%p == 0:
                flag = False
        if flag:
            primes.append(i)
    return primes
D = eratos2()

for i in range(1, 10**5+1):
    if i in D and (i+1)//2 in D:
        memo[i] = memo[i-1] + 1
    else:
        memo[i] = memo[i-1]

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
q = int(input())
l, r = [], []
for i in range(q):
    a, b = map(int, input().split())
    l.append(a)
    r.append(b)


like = [0] * 100001
prime = set()


def isprime(n):
    global prime
    if (n in prime):
        return True
    else:
        f = False
        for i in range(2, int(sqrt(n)) + 1):
            f |= (n % i == 0)

        if not f:
            prime.add(n)
        return not f


def is2017like(n):
    if n % 2 == 0:
        return False
    return isprime(n) & isprime((n + 1) // 2)


for i in range(1, 100001):
    like[i] = like[i-1] + int(is2017like(i))


for i in range(q):
    print(like[r[i]]-like[max(1, l[i]-1)])

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

l = []
r = []
while True:
  try:
    lr=list(map(int,input().split()))
    l.append(lr[0])
    r.append(lr[1])
  except:
    break

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

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

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

Submission status: Time Limit Exceeded

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

l = []
r = []
while True:
  try:
    lr=list(map(int,input().split()))
    l.append(lr[0])
    r.append(lr[1])
  except:
    break

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

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

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

Submission status: Time Limit Exceeded

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

l = []
r = []
while True:
  try:
    lr=list(map(int,input().split()))
    l.append(lr[0])
    r.append(lr[1])
  except:
    break

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

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for i in range(MAXI)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      if(prime[i] == 0):
        for j in range(i,MAXI,i*2):
          prime[j] = 0
  sn = [0]
  for i in range(1,MAXI+1,2):
    sn.append(prime[i] * prime[int((i+1)/2)]) #odd
    sn.append(0) #even
  return sn

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

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

    for i in range(Q):
        l,r=map(int,input().split())
        A=[0]*(r+1)
        for j in range(1,r+1,2):
            if j in primes and (j+1)//2 in primes:
                A[j]=1
        # 累積和を格納したリスト．A[l:r]の総和はB[r] - B[l]
        B = list(accumulate(A))
        print(B[r]-B[l-1])




resolve()

Submission status: Time Limit Exceeded

Solution code:
# abc084_d.py
'''
通常の素数判定（√N まで割り続ける方法）ではTLEするので
エラトステネスの篩をリストで用意しておく。
'''
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    return True

def is_like_num(n):
    return is_prime(n) and is_prime((n+1)//2)

erast_list = [is_like_num(i) for i in range(100001)]
# print(erast_list[:6].count(True))
# print(erast_list[:6])
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    print(erast_list[:R+1].count(True)-erast_list[:L].count(True))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            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 resolve():
    Q = I()
    lr = [LI() for _ in range(Q)]

    r_max = max([i[1] for i in lr])
    primes = sieve(r_max)

    acc = [0]*(r_max+2)
    for i in range(r_max+1):
        if i in primes and (i+1)//2 in primes:
            acc[i+1] = acc[i] + 1
        else:
            acc[i+1] = acc[i]

    for i in lr:
        print(acc[i[1]+1]-acc[i[0]])

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

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

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

for _ in range(q):
    l,r = map(int,input().split())
    tmp = len(set(sieve(r))-set(sieve(l-1)))
    print(tmp)