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


def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(x ** 0.5) + 1):
        # print("{}%{}".format(x, i))
        if x % i == 0:
            return False
    return True


for _ in range(q):
    l, r = map(int, input().split())
    if l % 2 == 0:
        l += 1
    count = 0
    for x in range(l, r + 1, 2):
        # print("x={}".format(x))
        if isPrime(x) and isPrime((x + 1) // 2):
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import math
import bisect

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    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 set(prime for prime in primes if prime != 0)


def is_prime(prime_list,a):
    return a in prime_list

def solve(Q: int, L: "List[int]", R: "List[int]"):
    prime_list = primes(10**5)

    for l,r in zip(L,R):
        ll = (l+1)//2
        rr = (r+1)//2
        res = 0
        for i,j in zip(range(l,r+1,2),range(ll,rr+1,1)):
            if is_prime(prime_list,i) and is_prime(prime_list,j):
                res += 1
        print(res)

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    Q = int(next(tokens))  # type: int
    l = [int()] * (Q)  # type: "List[int]" 
    r = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(Q, l, r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
numq = int(input())
lis = [1]*100001
lis[0] = 0
lis[1] = 0
i = 2
while(i < 318):
  if lis[i] == 1:
    k = 2
    while(i*k < 100001):
      lis[i*k] = 0
      k += 1
  i += 1
for _ in range(numq):
  count = 0
  a,b = map(int,input().split())
  for i in range(a,b+1):
    if i % 2 == 1 and lis[i] == lis[(i+1)//2] == 1:
      count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
numq = int(input())
lis = [1]*100001
lis[0] = 0
lis[1] = 0
i = 2
while(i < 318):
  if lis[i] == 1:
    k = 2
    while(i*k < 100001):
      lis[i*k] = 0
      k += 1
  i += 1
lis2 = [0]*100001

for i in range(1,100001):
  if i % 2 == 1 and lis[i] == lis[(i+1)//2] == 1:
    lis2[i] = 1

for _ in range(numq):
  a,b = map(int,input().split())
  print(sum(lis2[a:b+1]))

Submission status: Time Limit Exceeded

Solution code:
def sieve(n): # エラトステネスの篩
    num = [1]*n
    num[0]=num[1]= 0
    for i in range(int(n**0.5)+1):
        if num[i]:
            for j in range(i**2,n,i):
                num[j] = 0
    return num # list ### 1なら素数0なら合成数

primes = sieve(10**5)
like_2017 = []
for i in range(len(primes)):
    if i <= 2:
        like_2017.append(0)
    elif primes[i] == 1 and primes[(i+1)//2] == 1:
        like_2017.append(1)
    else:
        like_2017.append(0)
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(sum(like_2017[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
def prime_check(n):
    c=0
    for i in range(1,n+1):
        if n%i==0:
            c+=1
    return (True if c==2 else False)

n = int(input())
l= [list(map(int,input().split(" "))) for i in range(n)]
ans = []
for i in range(len(l)):
    c=0
    for j in range(l[i][0],l[i][1]+1):
        if prime_check(j) and prime_check((j+1)//2):
            c+=1
    ans.append(c)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
Q = int(input())
numberlist = [0 for i in range(100001)]
prime = [2]

for i in range(3, 100001, 2):
    flag = 1
    for j in prime:
        if i % j == 0:
            flag = 0
            break
    if flag == 1:
        prime.append(i)

for i in prime:
    if (i+1)//2 in prime:
        numberlist[i] += 1
for i in range(100000):
    numberlist[i+1] += numberlist[i]


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

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50

############
############
############

Q = i_inpl()
l, r = [], []

max_r = -INF
for _ in range(Q):
    li, ri = l_inpl()
    l.append(li)
    r.append(ri)
    max_r = max(max_r, ri)

table = list(range(2, max_r+1))
prime_table = []
while True:
    prime_num = table.pop(0)
    prime_table.append(prime_num)
    table = [ i for i in table if i % prime_num != 0]
    if len(table) == 0:
        break

# 1は2017に似てない数字
cumsums = [0]
for odd in range(3, max_r+3, 2):
    tmp = 0
    if odd in prime_table and (odd+1)//2 in prime_table:
        tmp += 1
    cumsums.append(cumsums[-1] + tmp)

for li, ri in zip(l, r):
    if li > 1:
        li = li//2 - 1
    else:
        li = 0
    ri = ri//2
    print(cumsums[ri]-cumsums[li])

Submission status: Time Limit Exceeded

Solution code:
import copy
Q = int(input())
lis = []
minimam = 10**5
maximam = 1
for _ in range(Q):
    l, r = map(int, input().split())
    lis.append((l, r))
    minimam = min(minimam, l)
    maximam = max(maximam, r)
flag_lis = [1] * (maximam+1)
flag_lis[0] = 0
flag_lis[1] = 0
for i in range(2, int((maximam-1)/2)+1):
    if flag_lis[i] != 0:
        for j in range(2*i,maximam+1,i):
            flag_lis[j] = 0
fin_lis = copy.copy(flag_lis)
for i in range(2, int((maximam+1)/2)+1):
    if flag_lis[i] == 0:
        fin_lis[2*i-1] = 0
for (l, r) in lis:
    count = 0
    for num in range(l,r+1,2):
        if fin_lis[num]==1:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def sosucheck(num):
    if num == 1:return False
    flag = True
    for i in range(1, int(num **(1/2))+1):
        if flag:
            flag = False
        else:
            if num % i == 0:
                return False
    return True
Q = int(input())
lis = []
minimam = 10**5
maximam = 1
for _ in range(Q):
    l, r = map(int, input().split())
    lis.append((l, r))
    minimam = min(minimam, l)
    maximam = max(maximam, r)
flag_lis = [0] * (maximam+1)
for num in range(minimam, maximam+1, 2):
    if sosucheck(num) and sosucheck((num+1)/2):
        flag_lis[num] = 1
    else:
        flag_lis[num] = 0
for (l, r) in lis:
    count = 0
    for num in range(l,r+1,2):
        if flag_lis[num]==1:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def sosucheck(num):
    if num == 1:return False
    flag = True
    for i in range(1, int(num **(1/2))+1):
        if flag:
            flag = False
        else:
            if num % i == 0:
                return False
    return True
Q = int(input())
lis = []
for _ in range(Q):
    l, r = map(int, input().split())
    lis.append((l, r))
for (l, r) in lis:
    count = 0
    for num in range(l,r+1,2):
        if sosucheck(num):
            if sosucheck((num+1)/2):
                count += 1
    print(count)

Submission status: Time Limit Exceeded

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

n = 10 ** 5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

like_numbers = []
for prime in primes:
    if int((prime + 1) / 2) in primes:
        like_numbers.append(prime)

for i in range(q):
    l = lr[i][0]
    r = lr[i][1]
    print(sum((x >= l and x <= r) for x in like_numbers))

Submission status: Time Limit Exceeded

Solution code:
import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    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]
primes = primes(10**5)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in primes:
        if (i+1)//2 in primes:
            cnt += 1
    dp[i] = cnt

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

Submission status: Time Limit Exceeded

Solution code:
import math
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
primes = primes(10**5)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in primes:
        if (i+1)//2 in primes:
            cnt += 1
    dp[i] = cnt

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

Submission status: Time Limit Exceeded

Solution code:
import math
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
primes = primes(10**5)
anss = []
for p in primes:
    if (p+1)//2 in primes:
        anss.append(p)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in anss:
        cnt += 1
    dp[i] = cnt

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

Submission status: Time Limit Exceeded

Solution code:
# D - 2017-like Number
# https://abc084.contest.atcoder.jp/tasks/abc084_d
import math

"""
累積和問題
"""

import sys

Q = int(sys.stdin.readline())
l_r = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]


def eratosthenes(num):
    """num以下の素数をエラトステネスの篩によって求める.リストをかえす"""
    prime = []
    limit = math.sqrt(num)
    data = [i for i in range(2, num + 1)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


"""
受けた数字は２次元配列で入ってくる
配列一つには、0に小さい方、１に大きいほうが入ってくる
なので、小さい方~大きい方までを展開して、その数と、２で割った数が素数であるかを調べる
"""

prime_numbers = eratosthenes(10**5+1)

for e in l_r:
    cnt = 0
    for n in range(e[0], e[1]+1):
        if n in prime_numbers and ((n + 1) // 2) in prime_numbers:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

def prime_table(n):
    list = [True for _ in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        if list[i]:
            j = i*2
            while j<=n:
                list[j] = False
                j += i
    table = [i for i in range(n+1) if list[i] and i>=2]
    return table

table = prime_table(10**5)
sim_sum = [0]*(10**5+1)
sim_sum[3] = 1
for i in range(5,10**5,2):
    if i in table and (i+1)//2 in table:
        sim_sum[i] = 1
    sim_sum[i] += sim_sum[i-2]
for l_ in l:
    print(sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)])

Submission status: Time Limit Exceeded

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

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

mc = max(l)[1]

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= len(prime):
        break

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

Submission status: Time Limit Exceeded

Solution code:
import math

def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    B = []
    C = [False for _ in range(limit + 4)]
    while True:
        a = min(A)
        if a > math.sqrt(limit):
            break
        B.append(a)
        i = 0
        while len(A) > i:
            if A[i] % a == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        B.append(a)
    for b in B:
        C[b] = True
    return C

def main():
    Q = int(input())
    lr = []
    mr = 0
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        lr.append((l, r))
        mr = max(mr, r)
    A = eratosthenes(mr)
    for l, r in lr:
        c = 0
        for i in range(l, r + 1, 2):
            if A[i] and A[(i + 1) // 2]:
                c += 1
        ans.append(c)
    for c in ans:
        print(c)


main()

Submission status: Time Limit Exceeded

Solution code:
import math

def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    B = []
    while True:
        a = min(A)
        if a > math.sqrt(limit):
            break
        B.append(a)
        i = 0
        while len(A) > i:
            if A[i] % a == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        B.append(a)
    return B

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


main()

Submission status: Time Limit Exceeded

Solution code:
def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check p+1 ~ p^2-1 (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return [i for i in range(ub+1) if prime[i]]

Q = int(input())
primes = sieve_of_eratosthenes(10**5)
cum_sum = [0]*(10**5+1)
for i in range(1, 10**5+1):
    if i in primes and (i+1) // 2 in primes:
        cum_sum[i] = cum_sum[i-1] + 1
    else:
        cum_sum[i] = cum_sum[i-1]

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
N = int(input())

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

sosu = primes(100000)
Sum = [0]*(len(sosu)+1)
for i in range(len(sosu)):
    if (sosu[i]+1)/2 in sosu:
        Sum[i+1] = Sum[i] + 1
    else:
        Sum[i+1] = Sum[i]

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
N = int(input())

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

sosu = primes(1000000)

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

Submission status: Time Limit Exceeded

Solution code:
import math

def is_prime(n):
    if n == 1:
        return False
    if not isinstance(n,int):
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

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

list_2017_similar=[]
for i in range(1,100000):
    if is_prime(i) == True and is_prime(int((i+1)/2)) == True and i != 2:
        list_2017_similar.append(i)

for i in range(Q):
    cnt=0
    for j in list_2017_similar:
        if L[i] <= j <= R[i]:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def is_like2017(X):
  res = 1
  for x in [X,(X+1)/2]:
    y = int(x**0.5)
    for i in range(2,y+1):
      if x%i==0:
        res=0
        break
    if res==0:
      break
  return res

prime = []
for i in range(10**5+2):
  if i<2 or i%2==0:
    prime.append(0)
  else:
    if is_like2017(i)==1:
      prime.append(1)
    else:
      prime.append(0)

#input
Q = int(input())
ans = []
for i in range(Q):
  l,r = map(int,input().split())
  print(sum(prime[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
def is_prime(x):
  res = 1
  y = int(x**0.5)
  for i in range(2,y+1):
    if x%i==0:
      res = 0
      break
  return res

prime = []
for i in range(10**5+2):
  if i<2 or i%2==0:
    prime.append(0)
  else:
    if is_prime(i)==1 and is_prime((i+1)/2)==1:
      prime.append(1)
    else:
      prime.append(0)
#input
Q = int(input())
ans = []
for i in range(Q):
  l,r = map(int,input().split())
  ans.append(sum(prime[l:r+1]))
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import accumulate

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

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 1

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

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

li = []
for i in range(3,max(R)+1,1):
    if is_prime(i) * is_prime((i+1)/2):
        li.append(1)
    else:
        li.append(0)
ans = [0, 0, 0]
ans += list(itertools.accumulate(li))
for i,j in zip(L,R):
    print(ans[j]-ans[i-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if (i+1) % 2 == 0 and is_prime3(i) == True:
			tmp = (i+1) / 2
			tmp = int(tmp)
			if is_prime3(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(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 is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if is_prime3(i) == True and (i+1) % 2 == 0:
			tmp = (i+1) / 2
			tmp = int(tmp)
			if is_prime3(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(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 is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if i in marix and (i+1) % 2 == 0:
			tmp = (i+1) / 2
			if tmp in marix:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(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]]
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	marix = getPrimeNumList(r_max)
	tergets = []
	for i in marix:
		if (i+1) % 2 == 0:
			tmp = (i+1) / 2
			if tmp in marix:
				tergets.append(i)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if i in tergets:
			counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(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]]
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	marix = getPrimeNumList(r_max)
	tergets = []
	for i in marix:
		if (i+1) % 2 == 0:
			tmp = (i+1) / 2
			if tmp in marix:
				tergets.append(i)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if i in marix and (i+1) % 2 == 0:
			tmp = (i+1) / 2
			if tmp in marix:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(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]]
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	marix = getPrimeNumList(r_max)
	tergets = []
	for i in marix:
		if (i+1) % 2 == 0:
			tmp = (i+1) / 2
			if tmp in marix:
				tergets.append(i)
				
	ans = []
	for i in maps:
		l, r = i
		counts1 = 0
		counts2 = 0
		for j in tergets:
			if j < l:
				counts1 += 1
				counts2 += 1
				continue
			if j <= r:
				#print(marix)
				counts2 += 1
		print(counts2 - counts1)
				
	
	
		
def getPrimeNumList(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]]
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
INF = float("inf")

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

# print(prime)
#import matplotlib.pyplot as plt
#plt.plot(prime[0:100])
#plt.show()

for i in range(len(prime)):
    if 2*i< prime[i]:
       continue

#    if prime[i] <i+1:
#        continue

    print(prime[i])



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)
        p1 = prime[xi-1]
        if p1 != i:
            continue

        i2 = (i+1)//2
        yi = bisect.bisect_right(prime, i2,lo = (xi+1)//2, 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
            break
                
    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)