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 sys
# import collections
# import math
# import bisect
# import re
# import itertools


def primeNums(n):
    from math import floor, sqrt
    sieve = set(range(2, n + 1))
    if 2 in sieve:
        not_prime = set(range(2 * 2, n + 1, 2))
        sieve -= not_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            not_prime = set(range(i * 2, n + 1, i))
            sieve -= not_prime
    return sieve

limit = 10 ** 5
prime_table = [0 for _ in range(limit + 1)]
for p in primeNums(limit):
    prime_table[p] = 1

like_2017_table = [0 for _ in range(limit + 1)]
for i in range(3, limit + 1, 2):
    if prime_table[i] and prime_table[(i + 1) // 2]:
            like_2017_table[i] = 1

def main():

    q = int(sys.stdin.readline().rstrip())
    m = map(int, sys.stdin.read().split())

    for l, r in zip(m, m):
        res = sum(like_2017_table[l:r + 1])
        print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
# import statistics

def primeNums(n):
    from math import floor, sqrt
    sieve = set(range(2, n + 1))
    if 2 in sieve:
        not_prime = set(range(2 * 2, n + 1, 2))
        sieve -= not_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            not_prime = set(range(i * 2, n + 1, i))
            sieve -= not_prime
    return sieve

limit = 10 ** 5
prime_table = [0 for _ in range(limit + 1)]
for p in primeNums(limit):
    prime_table[p] = 1

def main():

    q = int(sys.stdin.readline().rstrip())
    m = map(int, sys.stdin.read().split())

    for l, r in zip(m, m):
        res = 0
        for i in range(l if l % 2 == 1 else l + 1, r + 1, 2):
            res += (prime_table[(i + 1) // 2] if prime_table[i] else 0)
        
        print(res)


if __name__ == "__main__":
    # execute only if run as a script
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
# import statistics

def primeNums(n):
    from math import floor, sqrt
    sieve = set(range(2, n + 1))
    if 2 in sieve:
        not_prime = set(range(2 * 2, n + 1, 2))
        sieve -= not_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            not_prime = set(range(i * 2, n + 1, i))
            sieve -= not_prime
    return sieve

limit = 10 ** 5
prime_table = [0 for _ in range(limit + 1)]
for p in primeNums(limit):
    prime_table[p] = 1

def main():

    q = int(sys.stdin.readline().rstrip())
    lines = sys.stdin.readlines()
    
    for j in range(q):
        l, r = [int(x) for x in lines[j].split()]
        res = 0
        for i in range(l if l % 2 == 1 else l + 1, r + 1, 2):
            res += (prime_table[(i + 1) // 2] if prime_table[i] else 0)
        
        print(res)


if __name__ == "__main__":
    # execute only if run as a script
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

q = int(input())
for i in range(q):
  count = 0
  lr = [int(x) for x in input().split()]
  l = lr[0]
  r = lr[1]
  for j in range(l, r+1):
    if j==1:
      count-=1
    prime = True
    if math.sqrt(j)==int(math.sqrt(j)):
      prime=False
    if math.sqrt((j+1)/2)==int(math.sqrt((j+1)/2)):
      prime=False
    for k in range(2, int(math.sqrt(j))+1):
      if j%k==0:
        prime=False
        break   
    for k in range(2, int(math.sqrt((j+1)/2))+1):
      if ((j+1)/2)%k==0:
        prime=False
        break
    if prime==True:
      count+=1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
f=[True]*(10**5+1)
like=[False]*(10**5+1)
f[0]=False
f[1]=False
import math
for i in range(2,len(f)):
  fact=True
  for j in range(2,int(math.sqrt(i))+1):
    if i%j==0:
      fact=False
      break
  
  if fact:
    f[i]=True
    if i*2-1<len(like):
      like[i*2-1]=True
    for p in range(i*2,len(f),i):
      f[p]=False

Q=int(input())
for i in range(Q):
  l,r=map(int,input().split())
  cnt=0
  for p in range(l,r+1,2):
    if f[p] and like[p]:
      cnt+=1
  print(cnt)

Submission status: Time Limit Exceeded

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

max_range = math.sqrt(10**5)
list_search = [i for i in range(2, 10**5 + 1)]
list_prime = []
while list_search[0] <= max_range:
  list_prime.append(list_search[0])
  temp = list_search[0]
  list_search = [i for i in list_search if i % temp != 0]
list_prime.extend(list_search)

list_satisfy = []
for one_prime in list_prime:
  if one_prime * 2 > 10**5:
    break
  if one_prime * 2 - 1 in list_prime:
    list_satisfy.append(one_prime * 2 - 1)

result = [0 for _ in range(q)]
for one_num in list_satisfy:
  for i in range(q):
    if list_range[i][0] <= one_num <= list_range[i][1]:
      result[i] += 1
for one_result in result:
  print(one_result)

Submission status: Time Limit Exceeded

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

max_range = math.sqrt(10**5)
list_search = [i for i in range(2, 10**5 + 1)]
list_prime = []
while list_search[0] <= max_range:
  list_prime.append(list_search[0])
  temp = list_search[0]
  list_search = [i for i in list_search if i % temp != 0]
list_prime.extend(list_search)

list_satisfy = []
for one_prime in list_prime:
  if one_prime * 2 > 10**5:
    break
  if one_prime * 2 - 1 in list_prime:
    list_satisfy.append(one_prime * 2 - 1)

for l, r in list_range:
  result = len([i for i in list_satisfy if l <= i <= r])
  print(result)

Submission status: Time Limit Exceeded

Solution code:
isprimes = [True]*(10**5+1)
isprimes[0] = False
isprimes[1] = False
for i in range(2, 10**5+1):
  if isprimes[i]:
    j = i**2
    while j < 10**5+1:
      isprimes[j] = False
      j += i
Q = int(input())
for _ in range(Q):
  c = 0
  l, r = map(int, input().split())
  for x in range(l, r+1, 2):
    if isprimes[x] and isprimes[(x+1)//2]:
      c += 1
  print(c)

Submission status: Time Limit Exceeded

Solution code:
def div(x): #約数配列
    div=[1]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        if(x%check==0):
            div.append(check)
            while(x%check==0):
                x=x//check
        check+=1
    if x != 1:
      div.append(x)
    return div

def main():
    q=int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        ans=0
        for i in range((r-l)//2+1):
            if div(l+i*2)==[1,l+i*2] and div((l+i*2+1)//2)==[1,(l+i*2+1)//2]:
                ans+=1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
def like_2017(n):
    if n == 1: return False
    if n == 2: return False 

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

q = int(input())
L = [[int(i) for i in input().split()] for _ in range(q)]

for l,r in L:
    length = [i for i in range(l,r+1) if like_2017(i)]
    print(len(length))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

lr=[]
ma=0
for _ in range(N):
    l,r=map(int,input().split())
    ma=max(l,r,ma)
    lr.append([l,r])

#print(ma)

l=[0]*(ma+1)

for n in range(3,ma+1)[::2]:
    temp=(n*(n+1))//2
    flag=True
    for i in range(2,-int(-temp**0.5//1)):
        if temp%i==0:
            if i!=(n+1)//2:
                #print(n,i)
                flag=False
                break
    if flag:
        l[n]=l[n-2]+1
    else:
        l[n]=l[n-2]

#print(l)
for item in lr:
    print(l[item[1]]-l[item[0]] if l[item[0]-2]==l[item[0]] or item[0]==1 else l[item[1]]-l[item[0]]+1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

for _ in range(N):
    l,r=map(int,input().split())
    count=0
    for num in range(l,r+1)[::2]:
        temp=num*(num+1)//2
        flag=True
        for waru in range(2,(num+1)//2):
            if temp%waru==0:
                flag=False
                break
        if flag:
            count+=1
    print(count if l!=1 else count-1)

Submission status: Time Limit Exceeded

Solution code:
def isprime(x):
    for i in range(2 , int(x**0.5)+1):
        if x%i == 0:
            return False
    return True
N = 10**5
lst = []
for x in range(2,N):
    if isprime(x):
        lst.append(x)

q = int(input())
ans = []

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

for i in range(q):
    print(ans[i])

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

def islike(num):
    num1 = num
    num2 = (num+1)//2
    if (is_prime(num1) and is_prime(num2)):
        return True
    else:
        return False

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    total = 0
    for m in range(l, r+1):
        if islike(m):
            total += 1
    print(total)

Submission status: Time Limit Exceeded

Solution code:
p=int(input())
n = 10**5
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
lists=[]
for i in prime:
    lists.append(i)  
lists=sorted(lists) 
for i in range(p):
    count=0
    a,b=map(int,input().split())
    for j in range(a,b+1):
        if j in prime and (j+1)%2==0 and (j+1)//2 in prime:
            count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
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]
q = int(input())
rl = [map(int, input().split()) for _ in range(q)]

li = get_sieve_of_eratosthenes(10**5+1)
pli = [False] * (10**5+1)

for i in li:
  pli[i] = True

# print(li)
for l, r in rl:
  cnt = 0
  for j in range(l, r + 1):
    if j % 2 == 1 and pli[j] and pli[(j + 1) // 2]:
      cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
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]
q = int(input())
rl = [map(int, input().split()) for _ in range(q)]

li = set(get_sieve_of_eratosthenes(10**5))
# print(li)
for l, r in rl:
  cnt = 0
  for j in range(l, r + 1):
    if j % 2 == 1 and j in li and (j + 1) // 2 in li:
      cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
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]
q = int(input())
rl = [map(int, input().split()) for _ in range(q)]

li = get_sieve_of_eratosthenes(10**5)
# print(li)
for l, r in rl:
  cnt = 0
  for j in range(l, r + 1):
    if j % 2 == 1 and j in li and (j + 1) // 2 in li:
      cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline


# エラトステネスのふるい
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_list = [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_list + data
        prime_list.append(p)
        data = [e for e in data if e % p != 0]


prime = get_sieve_of_eratosthenes(10 ** 5)
p = set(prime)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    for i in prime[bisect_left(prime, l):bisect_right(prime, r)]:
        if (i + 1) // 2 in p:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
sys.setrecursionlimit(100000)

prime = [2]
def gcd(x,y):
    if y <= 0:
        return x
    return gcd(y,x%y)
  
#P以下の素数のリストを作成
def makePrime(P):
    for x in range(3,P+1,2):
        for y in prime:
            if gcd(x,y) == 1:
                if y == max(prime):
                    prime.append(x)
                continue
            else:
                break
                
Q = int(input())
cnt = 0
L = [0 for _ in range(Q) ]
R = [0 for _ in range(Q) ]

for i in range(Q):
    l, r = map(int,input().split())
    L[i], R[i] = l, r
makePrime(max(R))

for i in range(Q):
    l, r = L[i], R[i]
    j = l
    while l <= j and j <= r:
        if j in prime and (j+1)//2 in prime:
            cnt += 1
        j += 1
    print(cnt)
    cnt = 0

Submission status: Time Limit Exceeded

Solution code:
prime = []
def isPrime(n):
    if n == 1:
        return False
    if n in prime:
        return True
    k = 2
    while k*k <= n:
        if n%k==0:
            return False
        k += 1
    prime.append(n)
    return True

Q = int(input())
L = [0]*Q
R = [0]*Q
cnt = 0
for i in range(Q):
    l, r = map(int,input().split())
    j = l
    while l <= j and j <= r:
        if isPrime(j) and isPrime((j+1)//2):
            cnt += 1
        j += 1
    print(cnt)
    cnt = 0

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

q = int(input())
lr = []
for i in range(q):
    li, ri = map(int, input().split())
    lr.append([li, ri])

range_max = 100000
tf = np.ones(range_max, dtype=int)
tf[0] = 0

i = 1
while True:
    if i == int(range_max**(1/2))+1:
        break
    if not tf[i]:
        i += 1
        continue

    tmp = np.arange(i, range_max, i+1)
    tf[tmp[1:]] = 0
    i += 1


for i in range(q):
    tmp_index = np.arange(lr[i][0]-1, lr[i][1], 2)
    tmp_1 = tf[tmp_index]
    tmp_2 = tf[(lr[i][0]+1)//2-1:(lr[i][1]+1)//2]
    res = sum(tmp_1 * tmp_2)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
q=int(input())
x=[0]*q;y=[0]*q
for i in range(q):
    x[i],y[i]=map(int,input().split())
l=[]
for i in range(min(x),max(y)+1,2):
    d=prime_factorize(i)
    e=prime_factorize((i+1)//2)
    #print(d)
    if d==[i] and e==[(i+1)//2]:
        l.append(i)
#print(l)
for i in range(q):
    ans=0
    for j in range(len(l)):
        if x[i]<=l[j]<=y[i]:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
lr = []
for i in range(q):
    li, ri = map(int, input().split())
    lr.append([li, ri])

def isprime(n):
    if n == 1:
        return False
    elif n in [2, 3]:
        return True
    elif n % 2 == 0:
        return False
    elif n % 3 == 0:
        return False
    for i in range(3, int(n**(1/2))+1):
        if n % i == 0:
            return False
    return True

for i in range(q):
    res = 0
    for j in range(lr[i][0], lr[i][1]+1, 2):
        if isprime(j) and isprime((j+1)//2):
            res += 1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
def sosuu(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
ans=0
A=[list(map(int,input().split())) for _  in range(q) ]
for l , r in A:
    for i in range(l,r+1):
        if i%2!=0 and sosuu(i) and sosuu((i+1)/2):
            ans+=1
    print(ans)
    ans=0

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

primes = [0]
for i in range(1,10**5+3):
    if is_prime(i):
        primes.append(1)
    else:
        primes.append(0)

like20 = [0]
for i in range(1,10**5+3):
    if primes[i] == 1 and primes[(i+1) // 2] == 1:
        like20.append(1)
    else:
        like20.append(0)

for lr in lrs:
    l = lr[0]
    r = lr[1]
    print(sum(like20[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

primes = [0]
for i in range(1,10**5+3):
    if is_prime(i):
        primes.append(1)
    else:
        primes.append(0)

like20 = [0]
for i in range(1,10**5+3):
    if primes[i] == 1 and primes[(i+1) // 2] == 1:
        like20.append(1)
    else:
        like20.append(0)

for lr in lrs:
    l = lr[0]
    r = lr[1]
    print(like20[l:r+1].count(1))

Submission status: Time Limit Exceeded

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

# 0以上整数x未満の素数のリストを返す(0,1は含まない)
import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

import bisect

def main():
    N = 10**5+1
    ps = primes(N)
    P = [0]*N
    for p in ps:
        P[p] = 1

    Q = int(input())
    for _ in range(Q):
        ans = 0
        l,r = map(int, input().split())
        li = bisect.bisect_left(ps, l)
        ri = bisect.bisect_right(ps, r)
        for i in range(li, ri):
            if P[(ps[i]+1)//2]:
                ans += 1
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# 0以上整数x未満の素数のリストを返す(0,1は含まない)
import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def main():
    N = 10**5+1
    ps = primes(N)
    P = [0]*N
    for p in ps:
        P[p] = 1

    Q = int(input())
    for _ in range(Q):
        ans = 0
        l,r = map(int, input().split())
        for i in range(l, r+1):
            if P[i] and P[(i+1)//2]:
                ans += 1
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    is_prime=[True]*(n+1)
    is_prime[0],is_prime[1]=False,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]]

prime_number=prime(10**5)
number=[i for i in prime_number if (i+1)//2 in prime_number]

ans=[0]*(10**5+1)
for i in range(1,10**5):
    ans[i]=ans[i]+ans[i-1]
    if i in number:ans[i] +=1

for i in range(int(input())):
    a,b=map(int,input().split())
    print(ans[b]-ans[a-1])

Submission status: Time Limit Exceeded

Solution code:
number=[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]
for i in range(int(input())):
    a,b=map(int,input().split())
    count=0
    for i in range(len(number)):
        if a<=number[i]<=b:
            count +=1
        elif number[i]>b:break
    print(count)

Submission status: Time Limit Exceeded

Solution code:
prime=[True]*10**5
prime[0],prime[1]=False,False
for i in range(4,10**5,2):prime[i]=False
for i in range(3,int((10**5)**0.5)):
    if prime[i]==True:
        for j in range(i*2,10**5,i):
            prime[j]=False
prime=[i for i in range(len(prime)) if prime[i]==True]
number=[i for i in prime if (i+1)//2 in prime]

for i in range(int(input())):
    a,b=map(int,input().split())
    count=0
    for i in range(len(number)):
        if a<=number[i]<=b:
            count +=1
        elif number[i]>b:break
    print(count)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
l, r = [], []
for i in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
max_r = max(r)
sosu = set()

for i in range(2, max_r+1):
    for s in sosu:
        if i%s == 0:
            break
    else:
        sosu.add(i)
sums = [0] * (max_r + 1)
for i in range(1, max_r+1):
    if i in sosu and (i+1)//2 in sosu:
        sums[i] = sums[i-1] + 1
    else:
        sums[i] = sums[i-1]

for i in range(Q):
    print(sums[r[i]] - sums[l[i]-1])

Submission status: Time Limit Exceeded

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

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

def Eratosthenes(n):

    dp = [False]*n
    dp[0] = dp[1] = True
    prime = []
    for i in range(2,n):
        if dp[i]:
            continue
        prime.append(i)
        for j in range(i*2,n,i):
          dp[j] = True
    return prime

cnt = 0
for i in range(Q):
  E = Eratosthenes(LR[i][1]+1)
  #print(E)
  for j in E:
    if j >= LR[i][0] and isPrime(j) and isPrime((j + 1)//2):
      cnt += 1
  print(cnt)
  cnt = 0

Submission status: Time Limit Exceeded

Solution code:
def sieve_of_eratosthenes(N):
    prime_list = [True for _ in range(N + 1)]
    prime_list[0] = False
    prime_list[1] = False
    for p in range(2, int(N ** 0.5) + 1):
        if prime_list[p]:
            for i in range(2 * p, N + 1, p):
                prime_list[i] = False

    return prime_list


Q = int(input())
Max_ = 10**5
prime_list = sieve_of_eratosthenes(Max_)
prime_check_list = [0]*(Max_ + 1)
for i in range(1, Max_ + 1, 2):
    if prime_list[i] and prime_list[(i + 1) // 2]:
        prime_check_list[i] = 1
for _ in range(Q):
    l, r = map(int, input().split())
    print(sum(prime_check_list[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
import math


def sieve_of_eratosthenes(N):
    target_list = list(range(2, N+1))
    sqrt_N = math.sqrt(N)
    prime_list = []

    while True:
        min_ = min(target_list)
        if min_ >= sqrt_N:
            prime_list.extend(target_list)
            break
        prime_list.append(min_)
        i = 0
        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % min_ == 0:
                target_list.pop(i)
            i += 1

    return prime_list


Q = int(input())
prime_list = sieve_of_eratosthenes(10**5)
a_list = [0]*10**5
for i in range(1, 10**5, 2):
    if i in prime_list and (i + 1) / 2 in prime_list:
        a_list[i] = 1
ans = 0
for _ in range(Q):
    l, r = map(int, input().split())
    ans += sum(a_list[l:r+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

def eratos(n):
    if n == 1:
        return 0, 0
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    search_list = list(range(2,n+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
        if search_list[0] > math.sqrt(n):
            #prime_listにsearch_listを結合
            prime_list.extend(search_list)
            break
        else:
            #search_listの先頭をprime_listに入れる
            head_num = search_list[0]
            prime_list.append(head_num)
            #search_listの先頭をpopする
            search_list.pop(0)
            #head_numの倍数を取り除く
            search_list = [num for num in search_list if num % head_num != 0]

    p_list = np.array(prime_list)
    p_like = (p_list + 1) // 2
    inter = np.intersect1d(p_list, p_like)

    if (p_list[-1] + 1) // 2 == inter[-1]:
        return len(inter), 1
    else:
        return len(inter), 0


def main():
    Q = int(input())
    l = [None]*Q
    r = [None]*Q
    for i in range(Q):
        l[i], r[i] = map(int, input().split())
    
    for i in range(Q):
        R, _ = eratos(r[i])
        L, me = eratos(l[i])
        #print(l[i], L, r[i], R)
        print(R - L + me)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def eratosthenes(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]]
    return table


def main():
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]
    e = set(eratosthenes(10**5))

    for l, r in lr:
        cnt = 0
        for i in range(l, r+1, 2):
            if i in e and (i+1) // 2 in e:
                cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()