Problem:


Score : 400 points

Problem Statement

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

You are given Q queries.

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

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

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

Sample Input 1

1
3 7

Sample Output 1

2

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

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

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

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

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

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

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
print = sys.stdout.write

sieve = [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]

n = int(input())

for i in range(n):
    t = 0
    l,r = map(int,input().split())

    pos = 0
    while pos < len(sieve) and l > sieve[pos]:
        pos += 1

    while pos < len(sieve) and r >= sieve[pos]:
        t += 1
        pos += 1
    
    print(str(t)+"\n")

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=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 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:
def isPrime(n):
    if n==1:
        return(False)
    if n==2:
        return(True)
    for i in range(2,n):
        if n%i==0:
            return(False)
    return(True)

n =int(input())
c=[0]*n

for i in range(n):
    l,r=list(map(int,input().split()))
    for j in range(l,r+1,2):
        if isPrime(j) and isPrime(int((j+1)/2)):
            c[i]+=1
        
print('\n'.join([str(c) for c in c]))

Submission status: Time Limit Exceeded

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

import sys
import random

import functools


@functools.lru_cache(1024)
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


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) and is_prime3((i + 1) // 2):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8                                                                                         
import random

def is_prime(q,k=20):
    #計算するまでもなく判定できるものははじく                                                         
    if q < 2: return False # 2未満に素数はない                                                        
    if q == 2 or q == 3 or q == 5: return True # 2,3,5は素数                                          
    if q % 2 == 0 or q % 3 == 0 or q % 5 == 0: return False # 2,3,5の倍数は合成数                     

    #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())
LR = []
for i in range(Q):
    l, r = map(int, raw_input().split())
    LR.append((l, r))

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

Submission status: Time Limit Exceeded

Solution code:
import sys,math

_primes = {1:False,2:True}
like2017 = {}

def isPrime(num):
    if num not in _primes:
        for i in range(2,max(2,math.floor(math.sqrt(num))+1)):
            if num%i == 0:
                _primes[num] = False
                break
        else:
            _primes[num] = True
    return _primes[num]

def isLike(num):
    if num not in like2017:
        like2017[num] = True if (isPrime(num) and isPrime((num+1)/2)) else False
    return like2017[num]

Q = int(input())
for i in range(Q):
    S,G = list(map(int,input().split()))
    print(sum(isLike(x) for x in range(S,G+1,2)))

Submission status: Time Limit Exceeded

Solution code:
def prime(max):
  num = [True] * (max + 1)
  n = 2
  while n ** 2 <= max:
    if num[n]:
      m = n + n
      while m <= max:
        num[m] = False
        m += n
    n += 1
  return [i for i in range(2, max + 1) if num[i]]

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

prime = prime(max)

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

Submission status: Time Limit Exceeded

Solution code:

from math import sqrt, ceil
N = 100000

primeN = [True]*(N+1)
primeN[0] = primeN[1] = False
for i in range(2, ceil(sqrt(N+1))):
    if primeN[i]:
        primeN[i+i::i] = [False]*(len(primeN[i+i::i]))                            
#primeN = [ n for n in range(N+1) if temp[n] ]

n = int(input())
alst = []
primec = {}

for i in range(n):
    s = input().split()
    ans = 0
    
    for x in range(int(s[0]), int(s[1])+1, 2):
        ans += 1 if (primeN[x] and primeN[(x+1)//2]) else 0
    
    alst.append(ans)

for i in range(n):
    print(alst[i])

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 any(map(lambda i: num % i == 0, range(2, fl(sq(num)) + 1))) == False 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 primes(lower,upper):
    prime=[]
    for num in range(lower,upper + 1):
    	if num > 1:
	    	for i in range(2,num):
	    		if (num % i) == 0:
	    			break
	    	else:
	    		prime.append(num)
    return(prime)

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

q=int(input())
c=0

for i in range(q):
    n=list(map(int,input().split(" ")))
    p=primes(n[0],n[1])
    for i in p:
        if is_prime((i+1)/2):
            c+=1
    print(c)
    c=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 = {}
    for i in xrange(2, 10000):
        if is_prime(i):
            primes[i] = True

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

            counter = 0
            while l <= r:
                if l in primes and (l + 1) / 2 in primes:
                    counter += 1
                l += 2
            print counter

        line = sys.stdin.readline()

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

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8                                                                                         
import random

def is_prime(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 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())
LR = []
for i in range(Q):
    l, r = map(int, raw_input().split())
    LR.append((l, r))

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

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


@lru_cache(maxsize=None)
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

for l,r in lr_ary:
    ret=0
    for x in range(l,r+1,2):
        if is_prime(x) and is_prime((x+1)/2):
            ret += 1
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
import random
from math import sqrt, ceil

def is_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))
    if not temp[N]:
        return False
    return True

# スペース区切りの整数の入力
Q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

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]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

p = primes(10**5)

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

Submission status: Time Limit Exceeded

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

import sys
import random


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

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) and is_prime3((i+1)//2):
            ans+=1
    print(ans)

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

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

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

for i in range(q):
  if ran[i][0] % 2 == 0:
    j = ran[i][0]+1
  else:
    j = ran[i][0]
  count = 0
  while j <= ran[i][1] :
    if j in primes and ((j+1)//2) in primes:
      count += 1
    j += 2
  C.append(count)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math

def eratosthenes(l, 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 [i for i in prime_list if i >= l]

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

def is_prime(n):
    return len(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
    

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

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

Submission status: Time Limit Exceeded

Solution code:
import random
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

# スペース区切りの整数の入力
Q = int(input())

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

Submission status: Time Limit Exceeded

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

def isPrime(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, 1):
        if n % i == 0:
            return False
    return True



ls = []
rs = []
for n in range(Q):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
    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 isPrime(i) and isPrime((i+1)/2):
                num += 1
    print(num)

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

            counter = 0
            while l <= r:
                if is_prime(l) and is_prime((l + 1) / 2):
                    counter += 1
                l += 2
            print counter

        line = sys.stdin.readline()

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

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
lr = [list(map(int, input().split())) for i in range(Q)]
ok = []
for i in range(2, 50001):
    for j in range(2, int((i**0.5)+1)):
        if i%j == 0:
            break
    else:
        ok.append(i)

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

    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
point=[]
query=[]
for i in range(Q):
    l,r=[int(i) for i in input().split()]
    point.append(l)
    point.append(r)
    query.append([l,r])
# print(point)
point_uniq = list(set(point))
# print(point_uniq)
point_sorted = sorted(point_uniq)
# print(point_sorted)

#ふるい
SIZE=100001
is_prime=[True for i in range(SIZE)]
is_prime[0]=False
is_prime[1]=False
for i in range(2,SIZE):
    # print(i,is_prime)
    if is_prime[i]==False:
        continue
    else:
        tmp=i+i
        while(tmp<SIZE):
            is_prime[tmp]=False
            tmp+=i

MIN=point_sorted[0]
MAX=point_sorted[-1]
N_count=0
index=1
range_N=[]
for i in range(MIN,MAX+1):
    if i%2==0:
        continue
    if is_prime[i]==True and is_prime[int((i+1)/2)]==True:
        N_count+=1
    if i==point_sorted[index]:
        index+=1
        range_N.append([MIN,i,N_count])
# print(range_N)

for q in query:
    ans=0
    l_index=point_sorted.index(q[0])
    r_index=point_sorted.index(q[1])
    # print(q,l_index,r_index)
    if l_index==r_index:
        ans=1 if is_prime[q[0]] and is_prime[int((q[0]+1)/2)] else 0
    elif l_index==0:
        ans=range_N[r_index-1][2]
    else:
        ans=range_N[r_index-1][2]-range_N[l_index-1][2]
        if is_prime[q[0]] and is_prime[int((q[0]+1)/2)]:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = 100000
primeN = []
tmp = 2
for i in range(2, n):
    if primeN:
        for j in range(len(primeN)):
            if i % primeN[j] == 0:
                break
            else:
                if j == len(primeN) - 1:
                    primeN.append(i)
    else:
        if n > tmp:
            primeN.append(i)

n = int(input())
alst = []
primec = {}

for i in range(n):
    s = input().split()
    ans = 0
    
    for x in range(int(s[0]), int(s[1])+1, 2):
        ans += 1 if (primeN[x] and primeN[(x+1)//2]) else 0
    
    alst.append(ans)

for i in range(n):
    print(alst[i])

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

@lru_cache(maxsize=400000)
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

for l,r in lr_ary:
    ret=0
    for x in range(l,r+1,2):
        if is_prime(x) and is_prime((x+1)/2):
            ret += 1
    print(ret)

Submission status: Time Limit Exceeded

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

max_p = 10 ** 5

p = [0] * max_p
p[0] = 1
p[1] = 1

for x in range(2, math.floor(math.sqrt(max_p))):
    if p[x] is 0:
        for n in range(2, max_p // x):
            p[n * x] = 1

Q = int(input())

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

    cnt = 0
    for n in range((r - l) // 2 + 1):
        a = l + 2 * n
        if (p[a] is 0) and (p[(a + 1) // 2] is 0):
            cnt = cnt + 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8                                                                                      

import math

# 整数xが素数かどうかを判定する                                                                    
def is_prime(x):
    if x < 2: return False # 2未満に素数はない                                                     
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数                                       
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数                  

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく                      
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True


Q = int(raw_input())
LR = []
for i in range(Q):
    l, r = map(int, raw_input().split())
    LR.append((l, r))

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

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

@lru_cache(maxsize=300000)
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

rets = []
for l,r in lr_ary:
    ret=0
    for x in range(l,r+1,2):
        if is_prime(x) and is_prime((x+1)/2):
            ret += 1
    rets.append(ret)

for ret in rets:
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
import random

# Miller-Rabin test
def is_prime(q, k=50):
    q = abs(q)
    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(input())

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

Submission status: Time Limit Exceeded

Solution code:
import math
q = int(input())
l = [0 for i in range(q)]
r = [0 for i in range(q)]
for i in range(q):
    l[i], r[i] = list(map(int, input().split()))

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

def like(n):
    if prime(n):
        if prime((n+1)/2):
            return True
    return False

for i in range(q):
    count = 0
    for num in range(l[i], r[i]+1, 2):
        if like(num):
            count += 1
    print (count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

is_prime = lambda num: True if list(filter(lambda i: num % i == 0, range(2, num // 2 + 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)