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

    for j in range(l,r+1,2):
        if j in sieve:
            t += 1
    print(str(t)+"\n")

Submission status: Time Limit Exceeded

Solution code:
def is_prime(q):
	q = abs(q)
	if q == 2:
		return True
	if q < 2 or q & 1 == 0:
		return False
	else:
		return pow(2, q-1, q) == 1

def number_like2017(l,r):
	l = [i for i in range(l,r+1,2) if is_prime(i) and is_prime(int((i+1)/2))]
	print(len(l))


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

for i in P:
	number_like2017(i[0], i[1])

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import lru_cache

n=int(input())
@lru_cache()
def sosu(l):
  if l ==2:
    return 1
  elif l % 2==0 or l==1 or l==3/2:
    return 0
  else:
    for d in range(3, math.floor(math.sqrt(l))+1,2):
      if l % d == 0:
        return 0
        break
    else:
      return 1

li=[]
for j in range(1,100001):
  li.append(sosu(j)*sosu((j+1)/2))

for i in range(n):
  a,b=[int(i) for i in input().split()]
  print(sum(li[a-1:b]))

Submission status: Time Limit Exceeded

Solution code:
def is_prime(q):
	q = abs(q)
	if q == 2:
		return True
	if q < 2 or q & 1 == 0:
		return False
	else:
		return pow(2, q-1, q) == 1

def number_like2017(l,r):
	l = [i for i in range(l,r+1) if is_prime(i) and is_prime(int((i+1)/2))]
	print(len(l))


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

for i in P:
	number_like2017(i[0], i[1])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
sosu=[2]
for i in range(N):
  A,B=input().split(' ')
  A=int(A)
  B=int(B)
  count=0
  for j in range(B-2):
    j=j+3
    flag=0
    if j<=max(sosu): continue
    for k in sosu:
      if j%k==0:
        flag=1
        break
    if flag==0: sosu.append(j)
  for j in range(B-A+1):
    tmp=j+A
    if tmp in sosu and (tmp+1)/2 in sosu: count+=1
  print(count)

Submission status: Time Limit Exceeded

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

Carm = [561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361]

def isPrime(q):
  if q == 2:
    return True
  if q == 1 or q in Carm:
    return False
  return pow(2, q-1, q) == 1


C = []
for i in range(q):
  ran = list(map(int, input().split()))
  if ran[0] % 2 == 0:
    j = ran[0]+1
  else:
    j = ran[0]
  count = 0
  while j <= ran[1] :
    if isPrime(j) and isPrime((j+1)//2):
      count += 1
    j += 2
  C.append(count)

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

Submission status: Time Limit Exceeded

Solution code:
from math import *
import sys

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

sieve = set()

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

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

for n in range(1,10**5,2):
    if checkprime(n) and checkprime((n+1)/2):
        sieve.add(n)

n = int(input())

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

    for j in range(l,r+1,2):
        if j in sieve:
            t += 1
    print(str(t)+"\n")

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=100000)
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:
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(2, 100000):
    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:
def is_prime(q):
    if q in primec:
        return primec[q]
    if q == 2:
        primec[q] = True
        return True
    if q < 2 or q&1 == 0:
        primec[q] = False
        return False
    if pow(2, q-1, q) == 1:
        primec[q] = True
        return True
    else:
        primec[q] = False
        return False

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def is_prime_trial_division(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True
 

q = int(input())

plist = set()
for i in range(1,100000,2):
    if is_prime_trial_division(i):
        if is_prime_trial_division( int((i+1)/2) ):
            plist.add(i)

#print(plist)

for i in range(q):
    tl, tr = map(int,input().split(' '))
    cnt=0
    subs = set()
    for j in range(tl,tr+1,2):
        subs.add(j)
    cnt = len(plist.intersection(subs))
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
l=[ map(int,raw_input().split()) for i in range(N)]

a=[]
for m in l:
	cnt=0
	for i in range(m[0],m[1]+1):
		if i%2==0:
			continue
		elif i%3==0 and i!=3:
			continue
		else:
			if is_prime(i) and is_prime( (i+1)/2 ):
				cnt+=1
	a.append(cnt)


for i in a:
	print i

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
for i in range(N):
  A,B=input().split(' ')
  A=int(A)
  B=int(B)
  count=0
  sosu=[2]
  for j in range(B-2):
    j=j+3
    flag=0
    for k in sosu:
      if j%k==0:
        flag=1
        break
    if flag==0: sosu.append(j)
  for j in range(B-A+1):
    tmp=j+A
    if tmp in sosu and (tmp+1)/2 in sosu: count+=1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
def is_prime_trial_division(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True
 

q = int(input())

plist = set()
for i in range(100000):
    if is_prime_trial_division(i):
        if is_prime_trial_division( int((i+1)/2) ):
            plist.add(i)

#print(plist)

for i in range(q):
    tl, tr = map(int,input().split(' '))
    cnt=0
    subs = set()
    for j in range(tl,tr+1):
        subs.add(j)
    cnt = len(plist.intersection(subs))
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import lru_cache

n=int(input())
@lru_cache()
def sosu(l):
  
  if l ==2:
    return 1
  elif l % 2==0 or l==1 or l==3/2:
    return 0
  else:
    for d in range(3, math.floor(math.sqrt(l))+1,2):
      if l % d == 0:
        return 0
        break
    else:
      return 1

li=[]
for j in range(1,100001):
  li.append(sosu(j)*sosu((j+1)/2))

for i in range(n):
  a,b=[int(i) for i in input().split()]
  print(sum(li[a-1:b]))

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):
        if isPrime(i) and isPrime((i+1)/2):
            #print(l,r,i)
            num += 1
    print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
from collections import Counter
from itertools import permutations

def main():
    Q = int(input())
    LR = tuple(tuple(map(int, input().split())) for _ in [0] * Q)

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

def is_prime(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True

main()

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=1000)
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)