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:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec  2 18:42:44 2018
ABC084D
@author: maezawa
"""

n = int(10**5)
is_prime = [True]*(n+1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, n//2):
    if is_prime[i] == True:
        for j in range(2*i,n+1,i):
            is_prime[j] = False

prime_numbers = [i for i in range(n+1) if is_prime[i]]
similar = []

for i in prime_numbers:
    if (i+1) // 2 in prime_numbers:
        similar.append(i)
        
sim = [0]*(n+1)    
cnt = 0    
for i in range(n+1):
    if i in similar:
        cnt += 1
    sim[i]=cnt  

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

Submission status: Time Limit Exceeded

Solution code:
def is_prime(x):
  if x == 1:
    return False
  for i in range(2, x):
    if x % i == 0:
      return False
    if i * i>= x:
      break         #breakにしないと膨大な数字をいつまでも追いかけている
  return True

def check(l,r):
  count = 0
  for i in range(l,r+1,2):
    if is_prime(i) == True:
      if is_prime((i+1)//2) == True:
        count += 1
  return count


Q = int(input())

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


for i in nums:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
import math
def is_prime(x):
    if x == 2:
        return 1
    elif x % 2 == 0:
        return 0
    else:
        return pow(2, x - 1, x) == 1

def check(l,r):
  count = 0
  for i in range(l,r+1,2):
    if is_prime(i) == True and is_prime((i+1)//2) == True:
      count += 1
  return count


Q = int(input())

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


for i in nums:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
import math
def is_prime(x):
  if x == 1:
    return False
  for i in range(2, x):
    if x % i == 0:
      return False
    if i * i>= x:
      break         #breakにしないと膨大な数字をいつまでも追いかけている
  return True

def check(l,r):
  count = 0
  for i in range(l,r+1,2):
    if is_prime(i) == True and is_prime((i+1)//2) == True:
      count += 1
  return count


Q = int(input())

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


for i in nums:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
import math
Primes = {2}
Sim = [0 for i in range(100002)]

for i in range(3, 100001):
    if i % 2 == 0:
        Sim[i] = Sim[i-1]
    else:
        for p in Primes:
            if i % p == 0:
                Sim[i] = Sim[i-1]
                break
        else:
            Primes |= {i}
            if (i+1)//2 in Primes:
                Sim[i] = Sim[i-1] + 1
            else:
                Sim[i] = Sim[i-1]

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

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

# 0以上整数x「未満」の素数をリストに格納して返す
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]

def realprimes(y):
    Y = primes(y)
    t = int((y + 1) / 2)
    bestprime = []

    for prime in Y:
        if prime != 2:
            prime2 = (prime + 1)//2
            pw = 0
            for i in range(2,int(math.sqrt(prime2)) + 2):
                if prime2 == 2:
                    break
                elif prime2 % i == 0:
                    pw = 1
                    break
            if pw == 0:
                bestprime.append(prime)

    T = bestprime
    V = set(Y) & set(T)
    return list(V)
W = realprimes(10**5 - 1)
W.sort()

q = int(input())
s = []
for i in range(q):#h:高さ
    s.append([int(m) for m in input().split()])

ALL = [i + 1 for i in range(10**5)]
ALL2 = copy.deepcopy(ALL)

for i in range(q):
    ALL = ALL2[s[i][0] - 1:s[i][1]]
    length = len(set(ALL) & set(W))
    print(length)
    ALL = ALL2

Submission status: Time Limit Exceeded

Solution code:
import math

# 0以上整数x「未満」の素数をリストに格納して返す
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]

def realprimes(y):
    Y = primes(y)
    t = int((y + 1) / 2)
    bestprime = []

    for prime in Y:
        if prime != 2:
            prime2 = (prime + 1)//2
            pw = 0
            for i in range(2,int(math.sqrt(prime2)) + 2):
                if prime2 == 2:
                    break
                elif prime2 % i == 0:
                    pw = 1
                    break
            if pw == 0:
                bestprime.append(prime)

    T = bestprime
    V = set(Y) & set(T)
    return list(V)
W = realprimes(10**5 - 1)
W.sort()

q = int(input())
s = []
for i in range(q):#h:高さ
    s.append([int(m) for m in input().split()])
p = 0
p2 = 0
c = 0
c2 = 0
for i in range(q):
    while p == 0:
        if s[i][0] + c > s[i][1]:
            cut1 = 0
            break
        if s[i][0] + c in W:
            cut1 = W.index(s[i][0] + c)
            p = 1
        else:
            c += 1
    p = 0
    c = 0
    while p2 == 0:
        if s[i][1] - c2 < s[i][0]:
            cut2 = -1
            break
        if s[i][1] - c2 in W:
            cut2 = W.index(s[i][1] - c2)
            p2 = 1
        else:
            c2 += 1
    p2 = 0
    c2 = 0
    print(cut2 - cut1 + 1)

Submission status: Time Limit Exceeded

Solution code:
p,q,r = [2],[],[]
k = 3
while k < 100000:
  flag = True
  for t in p:
    if t*t > k:
      break
    if k%t == 0:
      flag = False
  if flag:
    p.append(k)
  k += 2
for t in p[1:]:
  if (t+1)//2 in p:
    q.append(t)
q.append(100000+3)
k = 0
for i in range(99999//2+1):
  while q[k]<=2*i+1:
    k += 1
  r.append(k)
c = int(input())
while c>0:
  x,y = map(int,input().split())
  print(r[y//2]-r[max(x,3)//2-1])
  c -= 1

Submission status: Time Limit Exceeded

Solution code:
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={i for i in primes if (i+1)//2 in primes}
q=int(input())
for i in range(q):
    a,b=map(int, input().split())
    print(len(set(range(a,b+1))&primes))

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
Qi=[]
x=0
def so(x):
    for i in range(int(x)-3):
        if x%(i+2)==0:
            return 0
    if x%x==0:
        return 1
    return 0
    
for i in range(Q):
    Qi.insert(i,input())
for i in Qi:
    cout=0
    i=i.split()
    for j in range(int(i[1])-int(i[0])+1):
        x=int(i[0])+j
        if x%2!=0 and x!=1:
            if so(x)==1 and so((x+1)/2)==1:
                cout+=1
    print(cout)

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
Qi=[]
x=0
def so(x):
    for i in range(int(x)-3):
        if x%(i+2)==0:
            return 0
    if x%x==0:
        return 1
    return 0
    
for i in range(Q):
    Qi.insert(i,input())
for i in Qi:
    cout=0
    i=i.split()
    for j in range(int(i[1])-int(i[0])+1):
        x=int(i[0])+j
        if x%2!=0 and x!=1:
            if so(x)==1:
                if so((x+1)/2)==1:
                    cout+=1
    print(cout)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(n**0.5)+1):
        if n % k == 0:
            return False
    return True

q = int(input())
for _ in range(q):
    c = 0
    l, r = map(int, input().split())
    for i in range(l, r+1):
        if is_prime(i):
            x = (i + 1) // 2
            if is_prime(x):
                c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
b=[]
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]]
a=primes(100000)
for i in range(q):
    l,r=map(int,input().split())
    cnt=0
    for j in a:
        if l<=j<=r:
            if (j+1)//2 in a:
                cnt+=1
        if r<=j:
            break
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
q=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]]
a=primes(100000)
for i in range(q):
    l,r=map(int,input().split())
    cnt=0
    for j in a:
        if l<=j<=r:
            if (j+1)//2 in a:
                cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(range(100000))
a[1] = 0
for p in a:
    if not p:
        continue
    elif p > 317:
        break
    else:
        for m in range(p + p, 100000, p):
            a[m] = 0
a = [x for x in a if x]
for i in range(n):
    l, r = map(int, input().split())
    ans = 0
    for x in range(l, r + 1, 2):
        if x in a and (x + 1) // 2 in a:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(p):
    if p == 1:
        return False
    for i in range(2, int(p ** .5) + 1):
        if p % i == 0:
            return False
    return True

n = int(input())
for i in range(n):
    l, r = map(int, input().split())
    ans = 0
    for x in range(l, r + 1, 2):
        if is_prime(x):
            if is_prime((x + 1) // 2):
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
Q = int(input())
query = []
rmax = -1
for _ in range(Q):
    line = list(map(int, input().split()))
    query.append(line)
    rmax = max(rmax, line[1])

prime = [2]

for x in range(3, rmax+1):
    pflag = True
    for n in prime:
        if x%n==0:
            pflag = False
            break
        if x<n*n:
            break
    if pflag:
        prime.append(x)
# print(prime)
acc = [0 for _ in range(rmax+1)]
for n in range(rmax+1):
    if n in prime and (n+1)//2 in prime:
        acc[n] += 1
    if n<rmax:
        acc[n+1] += acc[n]
# print(acc)
for q in query:
    print(acc[q[1]] - acc[q[0]-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
Q = int(input())

p = np.array([i for i in range(2*10**5+1)])
p[1]=0
for i in range(2,10**5):
    p[2*i::i] = 0
p = p[p!=0]

dic = {i:1 for i in p}
a = []
for i in range(len(p)):
    if dic.get((p[i]+1)//2,0)==1:
        a.append(p[i])
p=np.array(a)
for _ in range(Q):
    l,r = list(map(int,input().split()))
    tmp = p[l<=p]
    tmp = tmp[tmp<=r]
    print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
Q = int(input())

p = np.array([i for i in range(2*10**5+1)])
p[1]=0
for i in range(2,10**5):
    p[2*i::i] = 0
p = p[p!=0]

dic = {i:1 for i in p}

for _ in range(Q):
    l,r = list(map(int,input().split()))
    tmp = p[l<=p]
    tmp = tmp[tmp<=r]
    print([dic.get((x+1)//2,0)==1 for x in tmp].count(True))

Submission status: Time Limit Exceeded

Solution code:
import bisect
def prime_list(n):
    '''
    n未満の素数のリストを返す
    '''
    num = list(range(2, n))
    prime = []
    while num[0] ** 2 < n:
        p = num.pop(0)
        for j in range(2 * p, n, p):
            if j in num:
                num.remove(j)
        prime.append(p)
    prime += num
    return prime

Q = int(input())
queries = [list(map(int, input().split())) for _ in range(Q)]
primes = prime_list(10 ** 5)
prime_2017like = []
for prime in primes:
    if (prime + 1) // 2 in primes:
        prime_2017like.append(prime)
for i in range(Q):
    li, ri = queries[i]
    print(bisect.bisect_right(prime_2017like, ri) - bisect.bisect_right(prime_2017like, li - 1))

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

import math
def primes():
    n = 10**5
    sieve = [True] * (n + 1)
    for x in range(2, math.ceil(math.sqrt(n))):
        y = x * 2
        while y <= n:
            sieve[y] = False
            y += x
    return [i for (i, x) in enumerate(sieve[2:], 2) if x]

import bisect
def sub_p(l, r):
    li = bisect.bisect_left(list_p, l)
    ri = bisect.bisect_left(list_p, r)
    return list_p[li:ri+1]

list_p = primes()
set_p = set(list_p)

for _ in range(Q):
    l, r = map(int, input().split())
    sp = sub_p(l, r)
    
    ans = 0
    for p in sp:
        ans += ((p + 1) // 2) in set_p
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
PN = [i for i in range(100001)]
i = 2
while True:
    if i >= len(PN):
        break
    j = i * 2
    while True:
        if j >= len(PN):
            break
        PN[j] = 0
        j += i
    while True:
        i += 1
        if i >= len(PN):
            break
        if PN[i] != 0:
            break
PN[1] = 0
PN_2 = []
for i in range(100001):
    if PN[i] != 0 and PN[int((PN[i] + 1) / 2)] != 0:
        PN_2.append(PN[i])
    else:
        PN_2.append(0)

Q = int(input())
lr = []
for i in range(Q):
    cnt = 0
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        if PN_2[j] != 0:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
list1=[2]
list2=[]
for i in range(3,100000,2):
    flag=0
    for j in range(3,318):
        if i<j**2:
            break
        elif i%j==0:
            flag=1
            break
    #print(i,flag)
    if flag==0:
        list1.append(i)
        if (int((i+1)/2) in list1):
            list2.append(i)
#print(list1)
#print(list2)


N=int(input())
for k in range(N):
    A=input()
    A=A.rstrip().split(" ")
    A1=int(A[0])
    A2=int(A[1])
#print(A1,A2)
    cnt=0
    for l in list2:
        if A1<= l <=A2 :
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
list1=[2,3,5,7,11,13,17,19]
for i in range(21,100000,2):
    flag=0
    for j in range(3,318):
        if i%2==0:
            flag=1
            break
        elif i<j**2:
            break
        elif i%j==0:
            flag=1
            break
    #print(i,flag)
    if flag==0:
        list1.append(i)
#print(list1)

N=int(input())
for k in range(N):
    A=input()
    A=A.rstrip().split(" ")
    A1=int(A[0])
    A2=int(A[1])
#print(A1,A2)
    cnt=0
    for l in list1:
        if A1<= l <=A2 and (int((l+1)/2) in list1) :
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
list1=[2,3,5,7,11,13,17,19]
for i in range(20,100000):
    flag=0
    for j in range(3,318):
        if i%2==0:
            flag=1
            break
        elif i<j**2:
            break
        elif i%j==0:
            flag=1
            break
    #print(i,flag)
    if flag==0:
        list1.append(i)
#print(list1)

N=int(input())
for k in range(N):
    A=input()
    A=A.rstrip().split(" ")
    A1=int(A[0])
    A2=int(A[1])
#print(A1,A2)
    cnt=0
    for l in list1:
        if A1<= l <=A2 and (int((l+1)/2) in list1) :
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
def prime(n):
    seq = list(range(2, n))
    while len(seq) > 0:
        prime = seq.pop(0)
        yield prime
        # 素数で割り切れない数字のリストを作成
        seq = [i for i in seq if not i % prime == 0]

q=int(input())
l = []
r = []
for i in range(q):
    x,y = map(int,input().split())
    l.append(x)
    r.append(y)
ww = max(r)
a = list(prime(ww+1))

#print('a',a)

ans = [0]
for i in range(2,ww+1):
    if i in a:
        if (i+1)/2 in a:
            ans.append(ans[-1]+1)
        else:
            ans.append(ans[-1])
    else:
        ans.append(ans[-1])

#print(ans)

for i in range(0,q):
    if l[i] == 1:
        print(ans[r[i]-1])
    else:
        print(ans[r[i]-1]-ans[l[i]-2])

Submission status: Time Limit Exceeded

Solution code:
import bisect
def prime(n):
    seq = list(range(2, n))
    while len(seq) > 0:
        prime = seq.pop(0)
        yield prime
        # 素数で割り切れない数字のリストを作成
        seq = [i for i in seq if not i % prime == 0]

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

a = list(prime(max(r)+1))
#print('a',a)
c = []
for i in range(len(a)):
    if (a[i]+1)/2 in a:
        c.append(a[i])

c.sort()
#print('c',c)

for i in range(q):
    h = bisect.bisect_left(c,l[i])
    j = bisect.bisect_right(c,r[i])
    print(j-h)

Submission status: Time Limit Exceeded

Solution code:
def primes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * (int((n - i * i - 1) / (2 * i)) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


q = int(input())
array = [[int(x) for x in input().split()] for z in range(q)]

primes_array = primes(10000)

for l, r in array:
    res = 0
    l = l if l % 2 != 0 else l+1
    for num in range(l, r + 1, 2):
        if num % 2 == 0:
            continue
        if num in primes_array and (num + 1) // 2 in primes_array:
            res += 1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
def primes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * (int((n - i * i - 1) / (2 * i)) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


q = int(input())
array = [[int(x) for x in input().split()] for z in range(q)]

primes_array = primes(10000)

for l, r in array:
    res = 0
    for num in range(l, r + 1):
        if num % 2 == 0:
            continue
        if num in primes_array and (num + 1) // 2 in primes_array:
            res += 1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import math as m

def judge_prime(num):
    isPrime = [True]*(num+1)
    isPrime[0] = False
    isPrime[1] = False
    border = m.sqrt(num)
    i = 2
    while i <= border:
        if isPrime[i]:
            j = i*2
            while j <= num:
                isPrime[j] = False
                j += i
        i += 1
        
    #prime_list = []
    like2017_list = []
    for prime in range(3,num+1,2):
#        if isPrime[prime]:
#            prime_list.append(prime)
        if isPrime[int(prime)] and isPrime[int((prime+1)/2)]:
            like2017_list.append(prime)
        
    return like2017_list
        
    
    
def main():
    #input
#    Q1 = 1
#    LR1 = [[3,7]]
#    
#    Q2 = 4
#    LR2 = [[13, 13],
#                [7, 11],
#                [7, 11],
#                [2017, 2017]]
#    
#    
#    Q = Q2
#    LR = LR2
    
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, input().split())))

    # 1. find 2017-like number
    MAX_Q = 10**5
    
    like2017_list = judge_prime(MAX_Q)

    
    # judge
    for i in range(Q):
        print(sum([LR[i][0]<=like2017 <= LR[i ][1] for like2017 in like2017_list]))


    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math as m

def judge_prime(num):
    isPrime = [True]*(num+1)
    isPrime[0] = False
    isPrime[1] = False
    border = m.sqrt(num)
    i = 2
    while i <= border:
        if isPrime[i]:
            j = i*2
            while j <= num:
                isPrime[j] = False
                j += i
        i += 1
        
    prime_list = []
    for prime in range(num+1):
        if isPrime[prime]:
            prime_list.append(prime)
        
    return prime_list
        
    
    
def main():
    #input
    Q1 = 1
    LR1 = [[3,7]]
    
    Q2 = 4
    LR2 = [[13, 13],
                [7, 11],
                [7, 11],
                [2017, 2017]]
    
    
    Q = Q2
    LR = LR2

    # 1. find 2017-like number
    MAX_Q = 10**5
    
    prime_list = judge_prime(MAX_Q)
    
#    for i in range(MAX_Q+1):
    like2017_list = []
    for prime in prime_list:
        if (prime+1)/2 in prime_list:
            like2017_list.append(prime)
            
    
    # judge
    for i in range(Q):
        print(sum([LR[i][0]<=like2017 <= LR[i ][1] for like2017 in like2017_list]))


    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def primerange(lower, upper):
    from collections import deque
    result = deque()
    for num in range(lower, upper+1):
        if num > 1:
            for i in range(2,num):
                if (num % i) == 0:
                    break
            else:
                result.append(num)
    return result

def is_prime(n):
    if n == 2 or n == 3: return True
    if n < 2 or n%2 == 0: return False
    if n < 9: return True
    if n%3 == 0: return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        if n%f == 0: return False
        if n%(f+2) == 0: return False
        f += 6
    return True  

def main():
    from itertools import product, permutations, combinations, combinations_with_replacement
    import bisect

    Q = int(input())
    lr = [list(map(int, input().split())) for i in range(Q)]

    for l,r in lr:
        result = 0
        for i in primerange(l,r):
            tmp = (i+1)/2
            if is_prime(tmp):
                result += 1
        print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def get_prime_list(n):
    L = list(range(2,n+1))
    for i in range(2,int((n+1)**0.5)):
        if i not in L:
            continue
        L = [j for j in L if j <= i] + [j for j in L if j > i and j % i != 0]
    return L

Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
prime_list = get_prime_list(100000)
like_num = [i for i in prime_list if (i+1)//2 in prime_list]
for l,r in lr:
    print(len([i for i in like_num if l<=i<=r]))

Submission status: Time Limit Exceeded

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

querys = [list(map(int,input().split())) for x in range(Q)]

def siever(x):
  nums = [a for a in range(2,x+1)]
  primes = []
  while nums[0] <= int(math.sqrt(x))+1:
    tmp = nums.pop(0)
    primes.append(tmp)
    for num in nums:
      if num%tmp == 0:
        nums.remove(num)
        continue
  
  return (primes+nums)

L = 0
for query in querys:
  L = max(L,query[1])
primes = siever(L)
L2017= []
for prime in primes:
  if (prime+1)//2 in primes:
    L2017.append(prime)
result = [0]*(max(L2017)+1)
for l in L2017:
  result[l] = 1
for i in range(1,len(result)):
  result[i] += result[i-1]
for query in querys:
  if query[0] == query[1] and query[0] in L2017:
    print(1)
  else:
    if len(result) <= query[0]:
      print(0)
    elif len(result) <= query[1]:
      print(result[-1]-result[query[0]-1])
    else:
      print(result[query[1]]-result[query[0]-1])

Submission status: Time Limit Exceeded

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

querys = [list(map(int,input().split())) for x in range(Q)]

def siever(x):
  nums = [a for a in range(2,x+1)]
  primes = []
  while nums[0] <= int(math.sqrt(x))+1:
    tmp = nums.pop(0)
    primes.append(tmp)
    for num in nums:
      if num%tmp == 0:
        nums.remove(num)
        continue
  
  return (primes+nums)

L = 0
for query in querys:
  L = max(L,query[1])
primes = siever(L)
L2017= []
for prime in primes:
  if (prime+1)//2 in primes:
    L2017.append(prime)
for query in querys:
  if query[0] == query[1]:
    if query[0] in L2017:
      print(1)
    else:
      print(0)
  else: 
    print(bisect.bisect_right(L2017,query[1]) - bisect.bisect_left(L2017,query[0]))

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from itertools import accumulate

prime = [2]
more_prime = [0] * 100000
for i in range(3, 100000):
	j = 2
	while j <= sqrt(i):
		if i % j == 0:
			break
		j += 1
	else:
		prime.append(i)
		if (i + 1) // 2 in prime:
			more_prime[i-1] = 1

ans = list(accumulate(more_prime))

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

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は素数ではない
    x_sqrt = math.sqrt(x)  # 記憶させていちいち計算しない

    # エラトステネスのふるい
    for prime in primes:
        if prime == 0: continue  # 先に処理
        if prime > x_sqrt: break
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

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


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

    primes = [i for i in range(x)]
    primes[1] = 0  # 1は素数ではない
    x_sqrt = math.sqrt(x)  # 記憶させていちいち計算しない

    # エラトステネスのふるい
    for prime in primes:
        if prime == 0: continue  # 先に処理
        if prime > x_sqrt: break
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime*2-1 for prime in primes if prime != 0]


q = int(input())
array = [[int(x) for x in input().split()] for x in range(q)]
primes_array = set(primes(10000))
twoprimes_array = set(twoprimes(10000))

for item in array:
    tmp = range(item[0], item[1]+1, 2)
    res = set(tmp) & primes_array
    twores = set(tmp) & twoprimes_array
    print(len(res & twores))

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は素数ではない
    x_sqrt = math.sqrt(x)  # 記憶させていちいち計算しない

    # エラトステネスのふるい
    for prime in primes:
        if prime == 0: continue  # 先に処理
        if prime > x_sqrt: break
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

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


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

    primes = [i for i in range(x)]
    primes[1] = 0  # 1は素数ではない
    x_sqrt = math.sqrt(x)  # 記憶させていちいち計算しない

    # エラトステネスのふるい
    for prime in primes:
        if prime == 0: continue  # 先に処理
        if prime > x_sqrt: break
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime*2-1 for prime in primes if prime != 0]


q = int(input())
array = [[int(x) for x in input().split()] for x in range(q)]
primes_array = set(primes(10000))
twoprimes_array = set(twoprimes(10000))

for item in array:
    res = set(range(item[0], item[1]+1, 2)) & primes_array
    twores = set(range(item[0], item[1]+1, 2)) & twoprimes_array
    print(len(res & twores))

Submission status: Time Limit Exceeded

Solution code:
def primes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * (int((n - i * i - 1) / (2 * i)) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


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


q = int(input())
array = [[int(x) for x in input().split()] for y in range(q)]


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