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:
#!/usr/bin/env python3
# coding=utf-8

import sys
import random

import numpy as np


def is_prime3(q, k=50):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        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


like2017 = [1 if is_prime3(i) and is_prime3((i + 1) // 2) else 0 for i in range(100000 + 1)]
cumsum = np.cumsum(like2017)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print(cumsum[r] - cumsum[l-1])

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())
L = []
R = []
for i in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
    
def create_prime_number(n):
    a = [2, 3, 5, 7]
    
    for i in range(9, n+1, 2):
        pn = True
        line = math.sqrt(i)
        for j in a:
            if i % j == 0:
                pn =False
                break
            if j >= line:
                break
        if pn:
            a.append(i)
    return a

def is_like_2017(n):
    n2 = (n+1) / 2
    for i in PN:
        if n2 == i:
            return True
        if n2 < i:
            return False
    return False

def create_like_2017(a):
    ret = []
    i = 0
    for pn in a[1:]:
        n = (pn+1) // 2
        while n > a[i]:
            i += 1
        if n == a[i]:
            ret.append(pn)
    return ret

def get_x(n_min, n_max):
    x = 0
    for i in LIKE:
        if i >= n_min:
            x += 1
        if i > n_max:
            x -= 1
            return x
    return x

N_MIN = min(L)
N_MAX = max(R)

PN = create_prime_number(N_MAX)
LIKE = create_like_2017(PN)

for i in range(Q):
    x = get_x(L[i], R[i])
    print(x)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
a = []
for i in range(Q):
    a.append(list(map(int, input().split())))
number = []
prime_number = []
for i in range(1, 100000):
    number.append(i+1)
while number != []:
    prime_number.append(min(number))
    number = [x for x in number if x % min(number) != 0]
for i in range(Q):
    like_2017 = []
    for j in range(a[i][0], a[i][1] + 1, 2):        
        if (j in prime_number) and (int((j + 1) / 2) in prime_number):
            like_2017.append(j)
    print(len(like_2017))

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
a = []
for i in range(Q):
    a.append(list(map(int, input().split())))
number_list = []
for i in range(1,100000):
    number_list.append(i+1)
number_list_set = set(number_list)
prime_number_list = []
while True:
    try:
        prime_number_list.append(min(number_list_set))
        synthesis_number = {x for x in number_list if x % min(number_list_set) == 0}
        number_list_set = number_list_set - synthesis_number
    except:
        break
for i in range(Q):
    like_2017 = []
    for j in range(a[i][0], a[i][1] + 1, 2):        
        if (j in prime_number_list) and (int((j + 1) / 2) in prime_number_list):
            like_2017.append(j)
    print(len(like_2017))

Submission status: Time Limit Exceeded

Solution code:
num = [True]*(100001)
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

for i in range(100000, 1, -1):
  if not (num[i]):
    continue
  if not (num[int((i+1)/2)]):
    num[i] = False

for i in range(int(input())):
  _input = input().split(' ')
  sum = 0
  for i in range(int(_input[0]), int(_input[1])+1):
    if num[i]:
      sum = sum + 1
  print(sum)

Submission status: Time Limit Exceeded

Solution code:
num = [True]*(100001)
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

for i in range(int(input())):
  _input = input().split(' ')
  sum = 0
  for i in range(int(_input[0]), int(_input[1])+1):
    if (num[i]) and (num[int((i+1)/2)]):
      sum = sum + 1
  print(sum)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False

for i in range(Q):
  sum = 0
  if LR[i][0] % 2 == 0:
    for i in range(LR[i][0]+1, LR[i][1]+1, 2):
      if (num[i]) and (num[int((i+1)/2)]):
        sum = sum + 1
  else:
    for i in range(LR[i][0], LR[i][1]+1, 2):
      if (num[i]) and (num[int((i+1)/2)]):
        sum = sum + 1
  print(sum)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False
primeList = [i for i in range(2,max+1) if num[i]]

for i in range(Q):
  sum = 0
  if LR[i][0] % 2 == 0:
    for i in range(LR[i][0]+1, LR[i][1]+1, 2):
      if (i in primeList) and ((i+1)/2 in primeList):
        sum = sum + 1
  else:
    for i in range(LR[i][0], LR[i][1]+1, 2):
      if (i in primeList) and ((i+1)/2 in primeList):
        sum = sum + 1
  print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())
L = []
R = []
for i in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
def create_prime_number(n):
    a = [2, 3, 5, 7]
    
    for i in range(9, n+1, 2):
        pn = True
        line = math.sqrt(i)
        for j in a:
            if i % j == 0:
                pn =False
                break
            if j >= line:
                break
        if pn:
            a.append(i)
    return a

def is_like_2017(n):
    n2 = (n+1) / 2
    return (n in PN) and (n2 in PN)

def create_like_2017(a):
    ret = []
    for i in a:
        if is_like_2017(i):
            ret.append(i)
    return ret

def get_x(n_min, n_max):
    x = 0
    for i in LIKE:
        if i >= n_min:
            x += 1
        if i > n_max:
            x -= 1
            return x
    return x

N_MIN = min(L)
N_MAX = max(R)

PN = create_prime_number(N_MAX)
LIKE = create_like_2017(PN)

for i in range(Q):
    x = get_x(L[i], R[i])
    print(x)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False
primeList = [i for i in range(2,max+1) if num[i]]

for i in range(Q):
  sum = 0
  for i in range(LR[i][0], LR[i][1]+1):
    if (i in primeList) and ((i+1)/2 in primeList):
      sum = sum + 1
  print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def create_prime_number(n):
    a = [2, 3, 5, 7]
    
    for i in range(9, n+1, 2):
        line = math.sqrt(i)
        pn = True
        for j in filter(lambda x: x <= line, a):
            if i % j == 0:
                pn = False
                break
        if pn:
            a.append(i)
    return a

def is_like_2017(n):
    n2 = (n+1) / 2
    return (n in PN) and (n2 in PN)

def create_like_2017(n_min, n_max):
    a = []
    for i in range(n_min, n_max+1):
        if is_like_2017(i):
            a.append(i)
    return a

def get_x(n_min, n_max):
    x = 0
    for i in LIKE:
        if i >= n_min:
            x += 1
        if i > n_max:
            x -= 1
            return x
    return x

N_MIN = min(L)
N_MAX = max(R)

PN = create_prime_number(N_MAX)
LIKE = create_like_2017(N_MIN, N_MAX)

for i in range(Q):
    x = get_x(L[i], R[i])
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())
L = []
R = []
for i in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
    
def create_prime_number(n):
    a = [2, 3, 5, 7]
    
    for i in range(9, n+1, 2):
        line = math.sqrt(i)
        pn = True
        for j in filter(lambda x: x <= line, a):
            if i % j == 0:
                pn = False
                break
        if pn:
            a.append(i)
    return a

def is_like_2017(n):
    n2 = (n+1) / 2
    return (n in PN) and (n2 in PN)

def create_like_2017(n_min, n_max):
    a = []
    for i in range(n_min, n_max+1):
        if is_like_2017(i):
            a.append(i)
    return a

def get_x(n_min, n_max):
    c = 0
    for i in range(n_min, n_max+1):
        if i in LIKE:
            c += 1
    return c
  
N_MIN = min(L)
N_MAX = max(R)

PN = create_prime_number(N_MAX)
LIKE = create_like_2017(N_MIN, N_MAX)

for i in range(Q):
    x = get_x(L[i], R[i])
    print(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 30 22:48:07 2017

@author: kanako_note
"""
import numpy as np

def judge_sosu(num):
    if num == 1:
        return False
    divider = np.array([i for i in range(2,num)])
    
    if np.count_nonzero(num % divider)==divider.size or divider.size==0:
        return True
    else:
        return False

Q = int(input())
output = np.zeros(Q)
for i in range(Q):
    l, r = map(int, input().split())
    for j in range(l, r+1):
        if judge_sosu(j) and judge_sosu(int((j+1)/2)):
            output[i] += 1

for i in range(Q):
    print(int(output[i]))

Submission status: Time Limit Exceeded

Solution code:
primes = [[True]*100000][0]
for i in range(2,100000):
  if primes[i] == False:
    continue
  for j in range(2*i, 100000, i):
    primes[j] = False

c = [[False]*100000][0]

for i in range(3, 100000, 2):
  if primes[i] == False:
    continue
  if primes[(i+1)//2] == True:
    c[i] = True

q = int(input())
ran = []
for i in range(q):
  ran.append(list(map(int, input().split())))
for i in range(q):
  print(sum(c[:ran[i][1]+1])-sum(c[:ran[i][0]]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import math
import sys

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

    for i in xrange(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def main(argv):
    primes = [False]
    for i in xrange(1, 100000 + 1):
        primes.append(is_prime(i))

    results = [0]
    for i in xrange(1, 100000 + 1):
        if i % 2 == 0:
            results.append(0)
            continue

        if primes[i] and primes[(i + 1) / 2]:
            results.append(1)
        else:
            results.append(0)

    line = sys.stdin.readline()
    while line:
        Q = int(line.rstrip("\n"))
        for i in xrange(Q):
            l, r = map(
              lambda i: int(i), sys.stdin.readline().rstrip("\n").split(" "))

            print sum(results[l:r+1])

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
Q = int(input())

ls = []
rs = []
for n in range(Q):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
    num = 0

max_r = max(rs)

def eratos(n):
    if n == 1:
        return set()
    primes = [1 for i in range(n+1)]
    primes[0] = 0
    primes[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if primes[i] == 1:
            j = i + i
            while j <= n:
                primes[j] = 0
                j = j + i
    return primes


def count_similar(era, n):
    is_similar = [0 for i in range(n+1)]
    for i in range(n+1):
        if era[i] == 1 and era[int((i+1)/2)] == 1:
            is_similar[i] = 1
    count_similar = [0 for i in range(n+1)]
    for i in range(n+1):
        count_similar[i] = sum(is_similar[0:i+1])
    return count_similar




era = eratos(max_r)
cnt = count_similar(era, max_r)

for l, r in zip(ls, rs):
    print(cnt[r] - cnt[l-1])

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        prime2017[x] = 1
q=int(input())
lr_ary = []
for _ in range(q):
    l,r=list(map(int, input().split()))
    ret=sum(prime2017[l:r+1:2])
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        prime2017[x] = 1
q=int(input())
lr_ary = []
for _ in range(q):
    l,r=list(map(int, input().split()))
    ret=sum(prime2017[x] for x in range(l,r+1,2))
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""
q=int(input())
lr_ary = []
for _ in range(q):
  lr_ary.append(list(map(int, input().split())))

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        prime2017[x] = 1
for l,r in lr_ary:
    ret=sum(prime2017[x] for x in range(l,r+1,2))
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
Nl = [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]
Q = int(input())
R = []
for i in range(Q):
    R.append(list(map(int, input().split())))
for i in range(Q):
    tmp1 = 0
    tmp2 = 0
    for j in range(len(Nl)):
        if Nl[j - 1] < R[i][0] <= Nl[j]:
            tmp1 = j
            break
    for j in range(len(Nl)):
        if Nl[j - 1] <= R[i][1] < Nl[j]:
            tmp2 = j
            break
    print(tmp2 - tmp1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
Q = int(input())

ls = []
rs = []
for n in range(Q):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
    num = 0

max_r = max(rs)

def eratos(n):
    if n == 1:
        return set()
    primes = [1 for i in range(n+1)]
    primes[0] = 0
    primes[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if primes[i] == 1:
            j = i + i
            while j <= n:
                primes[j] = 0
                j = j + i
    return primes

era = eratos(max_r)


for l, r in zip(ls, rs):
    num = 0
    for i in range(l, r+1, 2):
        #print(i, isPrime(i), isPrime((i+1)/2), isPrime((i+1)/2))
        if ((i+1)/2)%2 == 0 and (i+1)/2 != 2:
            continue
        else:
            if era[i] == 1 and era[int((i+1)/2)] == 1:
                num += 1
    print(num)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# coding=utf-8

import sys
import random

import functools


@functools.lru_cache(100000)
def is_prime3(q, k=10):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        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


q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    ans = 0
    for i in range(l, r + 1, 2):
        if is_prime3((i + 1) // 2) and is_prime3(i):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def eratosthenes(r):
    prime_list = [i for i in (2, 3, 5) if i <= r]

    candidates = [i for i in range(2, r+1) if i % 2 and i % 3 and i % 5]
    while len(candidates):
        prime_list.append(candidates[0])
        candidates = [i for i in candidates[1:] if i % candidates[0]]
    return prime_list

def prime_decomposition(n):
    i = 2
    table = 0
    while i * i <= n:
        while n % i == 0:
            n /= i
            table += 1
        i += 1
    if n > 1:
        table += 1
    return table

def is_prime(n):
    return prime_decomposition(n) == 1

def similer_number_2017(l, r):
    # similar_numbers = []
    # for p in eratosthenes(l, r):
    #     if is_prime(int((p+1)/2)):
    #         similar_numbers.append(p)
    # return similar_numbers
    similar_num = 0
    multi = set()
    for i in range(max(l,2), r+1):
        if i in multi:
            continue
        if is_prime(i) and is_prime((i+1)/2):
            similar_num += 1
        multi.update([x for x in range(i, r+1, i)])
    return similar_num
    

Q = int(raw_input())
query = [map(int, raw_input().split(' ')) for _ in range(Q)]

for l, r in query:
    print similer_number_2017(l, r)

Submission status: Time Limit Exceeded

Solution code:
import math

def isPrime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

def binarySearch(num, lst):
    l = 0
    r = len(lst) - 1
    mid = int((l + r)/2)
    pivot = lst[mid]
    while (l <= r):
        if pivot == num:
            return True
        elif pivot > num:
            r = mid - 1
        else:
            l = mid + 1
        mid = int((l + r)/2)
        pivot = lst[mid]
    return False

q = int(input())
primes = set()
for i in range(1, 10001):
    if isPrime(i) == True:
        primes.add(i)

primes_list = list(primes)
primes_list = sorted(primes_list)
for i in range(q):
    cnt = 0
    l, r = [int(j) for j in input().split()]
    for j in range(l, r + 1):
        if binarySearch(j, primes_list) and binarySearch(int((j + 1)/2), primes_list):
            cnt += 1
    print (cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8
import random
Q = 0
L = []
R = []

# http://d.hatena.ne.jp/pashango_p/20090704/1246692091
def is_prime3(q,k=100):
    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 xrange(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

# 入力部分
Q = int(raw_input())
for i in range(Q):
  l, r = map(int, raw_input().split())
  L.append(l)
  R.append(r)

# 処理部分
for q in range(Q):
  cnt = 0
  for x in range(L[q], R[q]+1):
    if is_prime3(x) & is_prime3((x+1)/2):
      cnt += 1
  print cnt

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
n = 2 
num = [0]*(100001)
num[0] = -1
num[1] = 1
ans = 0
while n < 100001:
    i = n
    if num[i] != -1:
        num[i] = 1
        i += n
        while i < 100001:
            num[i] = -1
            i += n
    n += 1
for q in range(Q):
    l,r = map(int,input().split())
    ans = 0
    if l == r:
        if num[l] == 1:
            ans += 1
    else:
        for n in range(l,r):
            if n%2 == 1 and n != 1:
                m = int((n+1)/2)
                if num[n] == 1 and num[m] == 1:
                    ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

n = int(input())

sq = math.sqrt
fl = math.floor
is_prime = lambda num: True if num == 2 or pow(2, num - 1, num) == 1 else False

for i in range(n):
    l, r = map(int, input().split())
    l = 3 if l == 1 else l
    count = 0

    for j in range(l, r + 1, 2):
        if is_prime(j) and is_prime((j + 1) // 2):
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

def is_prime(x):
    if x < 2: return False
    if x == 2 or x == 3 or x == 5: return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False

    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

def my_chk(num):
    if is_prime(num):
        if is_prime((num+1)*0.5):
            return 1
        else:
            return 0
    else:
        return 0
    
if __name__ == '__main__':
    q = int(input())
    ans = []
    for i in range(q):
        info = list(map(int,input().split(" ")))
        chk_list = [ele for ele in range(info[0],info[1]+1,2)]
        temp = list(map(my_chk,chk_list))
        ans.append(sum(temp))
    for ele in ans:
        print(ele)

Submission status: Time Limit Exceeded

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


def isPrime(q):
  if q == 2:
    return True
  if q%2 == 0 or q == 1:
    return False
  j = 3
  while j <= math.sqrt(q):
    if q%j == 0:
      return False
    j += 2
  return True

C = []
ran = []
for i in range(q):
  ran.append(list(map(int, input().split())))

primes = []
for i in range(1, 100000):
  if isPrime(i):
    primes.append(i)

for i in range(q):
  count = 0
  for j in primes:
    if j < ran[i][0]:
      continue
    if j > ran[i][1] :
      break
    if ((j+1)//2) in primes:
      count += 1
  C.append(count)

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