Problem:


Score : 400 points

Problem Statement

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

You are given Q queries.

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

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

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

Sample Input 1

1
3 7

Sample Output 1

2

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

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

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

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

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

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

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy

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

prime = [0]*(10**5+1)
for i in range(1,10**5+1):
    prime[i] = is_prime(i)

q = int(input())
li = [0]*(10**5+1)
for i in range(1,10**5+1):
    if (i%2 == 1):
        if (prime[i] and prime[int((i+1)/2)]):
            li[i] = 1

com = numpy.cumsum(li)
for _ in range(q):
    l,r = [int(x) for x in input().split()]
    print(com[r]-com[l-1])

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy

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

q = int(input())
li = [0]*(10**5+1)
for i in range(1,10**5+1):
    if (i%2 == 1):
        if (is_prime(i) and is_prime((i+1)/2)):
            li[i] = 1

com = numpy.cumsum(li)
for _ in range(q):
    l,r = [int(x) for x in input().split()]
    print(com[r]-com[l-1])

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
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)

    return divisors
l=[]
r=[]
for i in range(Q):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)
ml=[]
c=[0 for i in range(10**5+1)]
for i in range(1,10**5+1,2):
    ml=make_divisors(i)
    if len(ml)==2:
        n=make_divisors((i+1)//2)
        if len(n)==2:
            c[i]=1
#print(c)
ans=[]
for i in range(Q):
    ad=sum(c[l[i]:r[i]+1])
    ans.append(ad)
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc084/tasks/abc084_d
from bisect import bisect_left, bisect_right
q = int(input())
queries = []
MAX = 0
for _ in range(q):
    l, r = map(int, input().split())
    queries.append((l, r))
    MAX = max([MAX, l, r])

def is_prime(x):
    sqrt = x ** 0.5
    i = 2
    while i <= sqrt:
        if x % i == 0:
            return False
        i += 1
    return True

def eratos(x):
    dp = [True] * (x + 1)
    dp[0] = dp[1] = False
    i = 2
    sqrt = x ** 2
    while i <= sqrt:
        for j in range(i * 2, x + 1, i):
            dp[j] = False
        i += 1
    primes = []
    for i in range(len(dp)):
        if dp[i]:
            primes.append(i)
    return primes, dp
primes, dp = eratos(MAX)
sub_prims = []
for p in primes:
    x = (p + 1) // 2
    if dp[x]:
        sub_prims.append(p)

for l, r in queries:
    left = bisect_left(sub_prims, l)
    right = bisect_left(sub_prims, r + 1)
    print(right - left)

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
A=[list(map(int,input().split())) for i in range(Q)]
B,C=zip(*A)
a=max(max(B),max(C))
def get_primenumber(N):
  prime_list=[2]
  for num in range(3,N+1,2):
    if all(num%prime != 0 for prime in prime_list):
      prime_list.append(num)
  return prime_list

X=get_primenumber(a)
P=[False]*(a+1)
L=[False]*(a+1)
for i in X:
  P[i]=True
for i in X:
  if P[(i+1)//2]:
    L[i]=True
C=[]
c=0
for i in range(a+1):
  if L[i]:
    c+=1
  C.append(c)
for s,t in A:
  print(C[t]-C[s-1])

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
L=[list(map(int,input().split())) for i in range(Q)]
A,B=zip(*L)
a=max(max(A),max(B))
def get_primenumber(N):
  #素数リスト
  prime_list = [2]
    #3からNまでの数字を一つずつ取り出す
  for num in range(3,N+1,2):
    #取り出した数字が素数リストの要素で割れなければ素数リストに追加する
    if all( num % prime != 0 for prime in prime_list):
      prime_list.append(num)
  return prime_list
X=get_primenumber(a)

def F(n):
  ans=0
  Z=get_primenumber(n)
  for i in Z:
    if (i+1)//2 in Z:
      ans+=1
  return ans

for s,t in L:
  print(F(t)-F(s-1))

Submission status: Time Limit Exceeded

Solution code:
import math
n = 100000
integer = [i for i in range(2,n+1)]
prime = []
like = []
while integer[0] <= math.sqrt(n):
    p = integer[0] 
    prime.append(p)
    integer = [i for i in integer if i % p != 0]
prime = prime + integer
for i in range(len(prime)):
    if ((prime[i]+1)//2) in prime:
        like.append(prime[i])
q = int(input())
for i in range(q):
    count = 0
    l,r = map(int,input().split())
    for j in range(l,r+1):
        if j in like:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

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


# 素数を表にする
primetable = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if is_prime(i):
        primetable[i] = 1
# 2017に似た数を表にする
like2017table = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if primetable[i] == 1 and \
        primetable[(i+1)//2] == 1:
        like2017table[i] = 1


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

for query in queries:
    begin = query[0]
    end = query[1]
    ans = sum(like2017table[begin:end+1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:


# 素数一覧を作成
primes = [ i for i in range(2, 100001) ]

for i in range(100001):
    for j in range(i+1, 100001):
        try:
            if primes[j] % primes[i] == 0:
                primes.pop(j)
        except IndexError:
            break

# 素数を表にする
primetable = [ 0 for i in range(100001) ]
for prime in primes:
    primetable[prime] = 1

# 2017に似た数を表にする
like2017table = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if primetable[i] == 1 and \
        primetable[(i+1)//2]:
        like2017table[i] = 1

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

for query in queries:
    begin = query[0]
    end = query[1]
    ans = sum(like2017table[begin:end+1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime_number(number):
    """素数判定プログラム.
    戻り値
    素数：True
    素数ではない：False
    """
    # 1,2,偶数は結果をそのまま返却
    if number == 1:
        return False
    elif number == 2:
        return True
    elif number % 2 == 0:
        return False
    else:
        pass

    # 3以上の奇数は入力値の1/2乗+1まで除算を行う
    for i in range(3,int(number ** (1 / 2)) + 1):
        if number % i == 0:
            # 一度でも割り切れたら素数ではない
            return False
    # 一度も割り切れなければ素数
    return True

n = int(input())
max_number = 0
number_list = []

for i in range(n):
  ans = 0
  a, b = map(int, input().split())
  for i in range(a, b+2, 2):
    if prime_number(i) == True and prime_number((i + 1)/2) == True:
      ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import datetime
import numpy as np

def sieve_of_eratosthenes(numbers):
    """指定された値までの素数を導出する関数.
    戻り値：
    素数のリスト
    """
    # 2から指定値までのndarrayを作成
    checker_np = np.array(range(2,numbers+1))

    # 素数を格納するリストを作成
    prime_list = []

    while len(checker_np) != 0:
        # リストの先頭（この値は必ず素数）を抽出
        _x = checker_np[0]
        # 取り出した値を素数リストに格納
        prime_list.append(_x)
        # ndarrayの中身のうち、抽出した素数で割り切れる値を除外
        # ※先頭の値が必ず最小の素数になる
        checker_np = np.delete(checker_np, np.where(checker_np % _x == 0))

    return prime_list

n = int(input())
max_number = 0
number_list = []

for i in range(n):
  a_list = list(map(int, input().split()))
  max_number = max(max_number, a_list[1])
  number_list.append(a_list)

prime_list = sieve_of_eratosthenes(max_number)
for i in number_list:
  ans = 0
  for j in range(i[0], i[1]+2, 2):
    if j in prime_list and (j + 1) / 2 in prime_list:
      ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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)

l_2017 = []
for p in primes[1:]:
    if (p+1)//2 in primes:
        l_2017.append(p)

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(l_2017, r) - bisect.bisect_left(l_2017, l))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

def prime_judge(n):
    Flg = True
    if n == 1:
        return False
    for i in range(2,int(n**0.5) + 1):
        if n % i == 0:
            Flg = False
            break
    if Flg:
        return True
    else:
        return False
#print(prime_judge(7))
q = int(input())
ans = 0

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

Submission status: Time Limit Exceeded

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

for _ in range(int(input())):
    l, r = map(int, input().split())
    c = [0] * (r + 1)

    check = []
    for i in range(l, r+1):
        if (i % 2 == 1):
            flg = (is_prime(i) and is_prime((i+1)/2))
        else:
            flg = 0
        check.append(flg)

    check = [0] + check
    check = list(accumulate(check))
    print(check[-1]-check[0])

Submission status: Time Limit Exceeded

Solution code:
import math


def eratos(num):
    isPrime = [True] * (num + 1)
    isPrime[0] = isPrime[1] = False
    for i in range(2, int(math.sqrt(num))):
        for j in range(2 * i, num, i):
            isPrime[j] = False
    return isPrime


def isLike(isPrime):
    n = len(isPrime)
    array = [False] * (n - 1)
    for i in range(n - 1):
        if isPrime[i] and isPrime[(i + 1) // 2]:
            array[i] = True
    return array


def solve(l, r, array):
    ans = 0
    for i in range(l, r + 1):
        ans += 1 if array[i] else 0
    return ans


Q = int(input())

isPrime = eratos(10 ** 5 + 1)
array = isLike(isPrime)

for i in range(Q):
    l, r = map(int, input().split())
    print(solve(l, r, array))

Submission status: Time Limit Exceeded

Solution code:
def is_prime(t):
  i=2
  while i**2<=t:
    if t%i==0:
      return 0
    i+=1
  return 1
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
n=10**5
p=[0]*(n+1)
d=[]
for i in range(2,n):
  if is_prime(i):
    d.append(i)
  if i in d and (i+1)//2 in d:
    p[i]=p[i-1]+1
  else:
    p[i]=p[i-1]
for l,r in lr:
  print(p[r]-p[l-1])

Submission status: Time Limit Exceeded

Solution code:
import bisect
q=int(input())
P=[2]
for i in range(3,10**5+2):
  for j in range(len(P)):
    if i%P[j]==0:
      break
    if j==len(P)-1:
      P.append(i)
p=set(P)
A=[]
for i in range(len(P)):
  if (P[i]+1)//2 in p:
    A.append(P[i])
for i in range(q):
  a,b=map(int,input().split())
  print(bisect.bisect_right(A,b+1,lo=0,hi=len(A))-bisect.bisect_right(A,a-1,lo=0,hi=len(A)))

Submission status: Time Limit Exceeded

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

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

s = [False] + [is_prime(i) for i in range(1, 10**5 + 1)]
s = [False] + [s[i] and s[(i + 1) // 2] for i in range(1, 10**5 + 1)]
cs = np.cumsum(s)

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
lr = zip(l,r)

def Is_prime(n):
    # nが1以下ならFalse
    if n<=1:
        return False
    # nが2または3ならTrue
    if n==2 or n==3:
        return True
    # nが2の倍数ならFalse
    if n%2==0:
        return False
    # nの平方根を整数で取得
    sqrt_root = int(n**.5)
    # nがnの平方根以下の3以上の奇数で1回でも割れたらFalse
    for i in range(3,sqrt_root+1,2):
        if n%i==0:
            return False
    # 上の条件を全てぬけたものはTrue
    return True

def Prime_table(n):
    res = []
    for i in range(n+1):
        if Is_prime(i):
            res.append(i)
    return res

ptb = Prime_table(max(r)+1)
def is_like(x):
    if x in ptb and (x+1)//2 in ptb:
        return 1
    return 0

L = list(itertools.accumulate(list(map(is_like,range(max(r)+1)))))

for l,r in lr:
    print(L[r]-L[l-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
lr = zip(l,r)

def Is_prime(n):
    # nが1以下ならFalse
    if n<=1:
        return False
    # nが2または3ならTrue
    if n==2 or n==3:
        return True
    # nが2の倍数ならFalse
    if n%2==0:
        return False
    # nの平方根を整数で取得
    sqrt_root = int(n**.5)
    # nがnの平方根以下の3以上の奇数で1回でも割れたらFalse
    for i in range(3,sqrt_root+1,2):
        if n%i==0:
            return False
    # 上の条件を全てぬけたものはTrue
    return True

def Prime_table(n):
    res = []
    for i in range(n+1):
        if Is_prime(i):
            res.append(i)
    return res

def is_like(x):
    ptb = Prime_table(x)
    if x in ptb and (x+1)//2 in ptb:
        return 1
    return 0

L = list(itertools.accumulate(list(map(is_like,range(max(r)+1)))))

for l,r in lr:
    print(L[r]-L[l-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
lr = zip(l,r)

def Is_prime(n):
    # nが1以下ならFalse
    if n<=1:
        return False
    # nが2または3ならTrue
    if n==2 or n==3:
        return True
    # nが2の倍数ならFalse
    if n%2==0:
        return False
    # nの平方根を整数で取得
    sqrt_root = int(n**.5)
    # nがnの平方根以下の3以上の奇数で1回でも割れたらFalse
    for i in range(3,sqrt_root+1,2):
        if n%i==0:
            return False
    # 上の条件を全てぬけたものはTrue
    return True

def Prime_table(n):
    res = []
    for i in range(n+1):
        if Is_prime(i):
            res.append(i)
    return res

def is_like(x):
    ptb = Prime_table(x)
    if x in ptb and (x+1)//2 in ptb:
        return 1
    return 0


for l,r in lr:
    L = list(itertools.accumulate(list(map(is_like,range(r+1)))))
    print(L[r]-L[l-1])

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
primes = [2]
for i in range(q):
    l, r = map(int,input().split())
    maxprime = primes[len(primes) - 1]
    if r > maxprime:
        for j in range(maxprime+1 if maxprime == 2 else maxprime+2, r+1, 2):
            #print(j)
            flag = True
            for prime in primes:
                if j % prime == 0:
                    flag = False
                    break
            if flag:
                primes.append(j)
    ans = 0
    for j in range(l, r+1):
        if j in primes and (j + 1) // 2 in primes:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(x):
    if x==1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True
    
def like2017_1tox(x):
    cnt=0
    for i in range(1,x+1,+2):
        if is_prime(i):
            if is_prime((i+1)//2):
                cnt+=1
        
    return cnt
    
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    print(like2017_1tox(b)-like2017_1tox(a-1))

Submission status: Time Limit Exceeded

Solution code:
def is_prime(x):
    if x==1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True
    
def like2017_1tox(x):
    cnt=0
    for i in range(1,x+1,+2):
        # print(i)
        if is_prime(i):
            if is_prime((i+1)//2):
                cnt+=1   
    return cnt
    
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    print(like2017_1tox(b)-like2017_1tox(a-1))

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
MAX = 10**5

def findAllOfPrime(N):
    prime = [True] * (N + 1)
    prime[0] = False
    prime[1] = False

    x = 2
    while x**2 <= N:
        if prime[x]:
            j = 2
            while x * j <= N:
                prime[x * j] = False
                j += 1
        x += 1

    return prime

prime = findAllOfPrime(MAX)

for _ in range(Q):
    cnt = 0
    l, r = map(int, input().split())

    for x in range(l, r + 1):
        if prime[x] and prime[(x + 1) // 2]:
            cnt += 1

    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
def era(n):
    data=[i for i in range(2,n+1)]
    for d in data:
        data=[x for x in data if(x==d or x%d != 0)]
    return data

Q=int(input())
l=[]
r=[]
up=0
for i in range(Q):
    a,b=map(int,input().split())
    up=max([up,a,b])
    
    l.append(a)
    r.append(b)
s=era(up)
like=[]

for i in range(len(s)):
    if((s[i]+1)/2==s[bisect.bisect_left(s,(s[i]+1)/2)]):
        like.append(s[i])
        
sumli=[0]*100001
tmp=0
for i in range(2,100001):
    if(i==like[tmp]):
        sumli[i]=sumli[i-1]+1
        if(tmp<(len(like)-1)):
            tmp+=1
    else:
        sumli[i]=sumli[i-1]

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
def era(n):
    data=[i for i in range(2,n+1)]
    for d in data:
        data=[x for x in data if(x==d or x%d != 0)]
    return data

Q=int(input())
l=[]
r=[]
up=0
for i in range(Q):
    a,b=map(int,input().split())
    up=max([up,a,b])
    
    l.append(a)
    r.append(b)
s=era(up)
like=[]

for i in range(len(s)):
    if((s[i]+1)/2==s[bisect.bisect_left(s,(s[i]+1)/2)]):
        like.append(s[i])

for i in range(Q):
    left=bisect.bisect_left(like,l[i])
    right=bisect.bisect_right(like,r[i])
    print(right-left)

Submission status: Time Limit Exceeded

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

primelist=get_sieve_of_eratosthenes_new(10**5)
subprimelist=[(primelist[i]+1)//2 for i in range(0,len(primelist))]
primeset=set(primelist)
subprimeset=set(subprimelist)
real=list(primeset&subprimeset)
real=[2*real[i]-1 for i in range(0,len(real))]
real=set(real)

Q=int(input())
l=[0]*Q
r=[0]*Q
for i in range(0,Q):
    l[i],r[i]=map(int,input().split())
for i in range(0,Q):
    test={i for i in range(l[i],r[i]+1)}
    print(len(test&real))

Submission status: Time Limit Exceeded

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

primelist=get_sieve_of_eratosthenes_new(10**5)
subprimelist=[(primelist[i]+1)//2 for i in range(0,len(primelist))]
primeset=set(primelist)
subprimeset=set(subprimelist)
real=list(primeset&subprimeset)
real=[2*real[i]-1 for i in range(0,len(real))]
real=set(real)

Q=int(input())
l=[0]*Q
r=[0]*Q
for i in range(0,Q):
    l[i],r[i]=map(int,input().split())
for i in range(0,Q):
    test={i for i in range(l[i],r[i]+1)}
    print(len(test&real))

Submission status: Time Limit Exceeded

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


def solve(Q: int, l: "List[int]", r: "List[int]"):
    # 10^5までの素数を予め計算しておく。
    INF = 100100
    is_prime = get_prime_numbers_array(INF)
    for i in range(Q):
        cnt = 0
        for j in range(l[i], r[i] + 1):
            if j % 2 == 0:
                continue
            if (is_prime[j] and is_prime[int((j+1)/2)]):
                cnt += 1
        print(cnt)
    return

def get_prime_numbers_array(n):
    """エラトステネスのふるいを用いてnまでの素数判定を行うための配列を返す

    Args:
        n ([int]): nまでの素数判定を行う
    """
    N = n + 1
    is_prime = [1] * N
    is_prime[0] = is_prime[1] = 0
    for i in range(2, N):
        if not is_prime[i]:
            continue
        for j in range(i * 2, N, i):
            is_prime[j] = 0
    return is_prime


# Generated by 1.1.6 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:
q = int(input())
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

a = [0 for i in range(10**5+1)]
for i in range(1,10**5+1,2):
	if is_prime(i) and is_prime((i+1)//2):
		a[i] = 1

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

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
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
#判定済み
a = []
#素数
b = []
for i in range(q):
	l, r = map(int, input().split())
	cnt = 0
	for j in range(l, r+1):
		if j%2 == 1:
			if j in a:
				if j in b:
					cnt += 1
				continue
			a.append(j)
			if is_prime(j) and is_prime((j+1)//2):
				b.append(j)
				cnt += 1
	print (cnt)

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())

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)

from bisect import bisect_left,bisect_right
lr=[]
for i in range(Q):
    lr=list(map(int, input().split()))
    left=bisect_left(primes, lr[0])
    right=bisect_right(primes, lr[1])
    cnt=0
    for p in primes[left:right]:
        if p!=2:
            if primes[bisect_left(primes,(p+1)//2)]==(p+1)//2:
                cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())

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)

from bisect import bisect_left,bisect_right
lr=[]
for i in range(Q):
    lr=list(map(int, input().split()))
    left=bisect_left(primes, lr[0])
    right=bisect_right(primes, lr[1])
    cnt=0
    for p in primes[left:right]:
        if p!=2 and (p+1)//2 in primes:
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
U = 10**5+10
T = np.zeros(U, np.bool)
T[1] = 1
T[2] = 1
T[3::2] = 1
for i in range(3,U,2):
  if i*i>U:
    break
  if T[i]:
    T[i*i::i+i] = 0
A = np.zeros(U, np.bool)
for i in range(U):
  if T[i]==1 and T[(i+1)//2]==1:
     A[i] = 1
A[1] = 0
A[2] = 0
A = A.cumsum()
    
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  print(A[r]-A[l-1])

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())

PN=[-1]*(10**5+1)
PN[0]=0
PN[1]=0

def PN_chk(n):
    if PN[n]==1:return True
    elif PN[n]==0:return False
    else:
        for i in range(2,int(int(n**0.5)+1)):
            if n%i==0:
                PN[n]=0
                return False
        PN[n]=1
        return True


chk=[-1]*(10**5+1)

def YN(n):
    if chk[n]==1:return True
    elif chk[n]==0:return False
    else:
        if PN_chk(n)==True and PN_chk((n+1)//2)==True:
            chk[n]=1
            return True
        else:
            chk[n]=0
            return False

for i in range(Q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r+1,2):
        if YN(j):ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())

PN=[True]*(10**5+1)
PN[0]=False
PN[1]=False

for i in range(2,int(int(10**5)**0.5+1)):
    if PN[i]==True:
        cnt=2
        while i*cnt<10**5+1:
            PN[i*cnt]=False
            cnt+=1

chk=[-1]*(10**5+1)

def YN(n):
    if chk[n]==1:return True
    elif chk[n]==0:return False
    else:
        if PN[n]==True and PN[(n+1)//2]==True:
            chk[n]=1
            return True
        else:
            chk[n]=0
            return False

for i in range(Q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r+1,2):
        if YN(j):ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def isPrime(a):
  i = 2
  while i <= int(a**(1/2)):
    if a % i == 0:
      return False
    if i == 2:
      i = i + 1
    else:
      i = i + 2
  return True


q = int(input())

l = []
r = []
ans = []
for _ in range(q):
  t1, t2 = map(int, input().split())
  l.append(t1)
  r.append(t2)

for i in range(q):
  cnt = 0
  for j in range(l[i], r[i]+1):
    if j % 2 != 0 and j != 1:
      if isPrime(j) and isPrime((j+1)/2):
        cnt = cnt + 1
  ans.append(cnt)
  
for _ in range(len(ans)):
  print(ans[_])

Submission status: Time Limit Exceeded

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

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

tmp=max([a[i][1] for i in range(q)])+1
primes=erato(tmp)
#print(primes)
imos=[0]*(tmp)
for i in range(3,tmp):
    if i%2==1:
      if i in primes and (i+1)//2 in primes:
          imos[i]=imos[i-2]+1
      else:
          imos[i]=imos[i-2]
    if i%2==0:
      imos[i]=imos[i-1]
#print(imos)
for i in range(q):
    print(imos[a[i][1]]-imos[a[i][0]-1])

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

def is_primenumber(n):
    if n == 1: return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0: return False
    return True

for i in range(Q):
    l, r = [int(n) for n in input().split()]
    c = 0
    for j in range(l, r+1, 2):
        if (is_primenumber(j) and is_primenumber((j+1)//2)):
            c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import sqrt

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

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

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

    return True


# メモ化
dd = defaultdict(bool)

for l, r in lr:
    count = 0
    for i in range(l, r+1, 2):
        if dd[i]:
            count += 1
        else:
            dd[i] = is_prime(i) & is_prime((i+1)//2)
            if dd[i]:
                count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys


def make_primes(n):
    primes = [2]
    for i in range(3, n, 2):
        if is_prime(i, primes):
            primes.append(i)
    return primes


def is_prime(n, primes):
    for prime in primes:
        if n % prime == 0:
            return False
        if n // 2 < prime:
            break
    return True


def make_like2017():
    like2017 = [0]
    for idx in range(1, len(primes)):
        if is_prime((primes[idx] + 1) // 2, primes):
            like2017.append(like2017[idx - 1] + 1)
        else:
            like2017.append(like2017[idx - 1])
    return like2017


def sol(l, r):
    if l == r:
        if is_prime(l, primes) and is_prime((l + 1) // 2, primes):
            return 1
        else:
            return 0

    idx_l = bisect.bisect_left(primes, l)
    idx_r = bisect.bisect_left(primes, r)

    if idx_l == idx_r:
        return 0
    else:
        idx_l = max(0, idx_l - 1)
        idx_r = min(len(like2017s) - 1, idx_r)
        return like2017s[idx_r] - like2017s[idx_l]


N_MAX = 10 ** 5 + 1

Q = int(sys.stdin.readline())
primes = make_primes(N_MAX)
like2017s = make_like2017()

for _ in range(Q):
    l, r = map(int, sys.stdin.readline().split())
    print(sol(l, r))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys


def make_primes(n):
    primes = [2]
    for i in range(3, n, 2):
        if all(i % prime != 0 for prime in primes):
            primes.append(i)
    return primes


def make_like2017():
    like2017 = [0]
    for idx in range(1, len(primes)):
        if (primes[idx] + 1) // 2 in primes:
            like2017.append(like2017[idx - 1] + 1)
        else:
            like2017.append(like2017[idx - 1])
    return like2017


def sol(l, r):
    if l == r:
        if l in primes and (l + 1) // 2 in primes:
            return 1
        else:
            return 0

    idx_l = bisect.bisect_left(primes, l)
    idx_r = bisect.bisect_left(primes, r)

    if idx_l == idx_r:
        return 0
    else:
        idx_l = max(0, idx_l - 1)
        idx_r = min(len(like2017s) - 1, idx_r)
        return like2017s[idx_r] - like2017s[idx_l]


N_MAX = 10 ** 5 + 1

Q = int(sys.stdin.readline())
primes = make_primes(N_MAX)
like2017s = make_like2017()

for _ in range(Q):
    l, r = map(int, sys.stdin.readline().split())
    print(sol(l, r))

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
n = 10 ** 5
L = [0] * 2 + [1] * (n-1)

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

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
lr = []
maxr = 0
for i in range(Q):
    l,r = map(int,input().split())
    maxr = max(maxr,r)
    lr.append([l,r])
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]]
prime2 = primes(maxr)
prime = [i for i in prime2 if (i+1)/2 in prime2]
import bisect
for l,r in lr:
    print(bisect.bisect_right(prime,r)-bisect.bisect_right(prime,l-1))