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: Wrong Answer

Solution code:
def prime(n):
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return [i for i in range(2,n) if num[i]]

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(2*i,M+1,i):
            P[j]=False
C=[0 for i in range(M+1)]
for i in range(M+1):
    if P[i] and P[(i+1)//2]:
        print(i)
        for j in range(i,M+1):
            C[j]+=1

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

Submission status: Wrong Answer

Solution code:
import math

tb = [0 for x in range(10**5 + 1)]
so = {2:True}
for i in range(3, 10**5 + 1):
  flag = True
  for s in so:
    if i % s == 0:
      flag = False
      break
    if s > math.sqrt(i):
      break
  if flag:
    so[i] = True

prev = 2
count = 0
for x in so:
  if x == 2:
    continue
  n2 = (x + 1) // 2
  if n2 in so:
    for j in range(prev, x):
      tb[j] = count
    prev = x
    count += 1

q = int(input())
L = []
r = []
for i in range(q):
  L += [0]
  r += [0]
  L[i], r[i] = [int(x) for x in input().split()]
for i in range(q):
  res = tb[r[i]] - tb[L[i]]
  if tb[L[i]] != tb[L[i] - 1]:
    res += 1
  print(res)

Submission status: Wrong Answer

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, 10000 + 1):
        primes.append(is_prime(i))

    results = [0]
    for i in xrange(1, 10000 + 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: Wrong Answer

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  int((i+1)/2) in plist or is_prime_trial_division(int((i+1)/2)):
            plist.add(i)

#print(plist)

pcnt=[]
cnt=1
for i in range(100000):
    if i in plist:
#        print("cnt", i)
        cnt+=1
    pcnt.append(cnt)

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)
#        if j in plist:
#            cnt +=1
    ans=pcnt[tr-1]-pcnt[tl-1]
#    print(tr, pcnt[tr])
#    print(tl, pcnt[tl])
    print(ans)

Submission status: Wrong Answer

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  int((i+1)/2) in plist or is_prime_trial_division(int((i+1)/2)):
            plist.add(i)

#print(plist)

pcnt=[]
cnt=1
for i in range(100000):
    if i in plist:
        print("cnt", i)
        cnt+=1
    pcnt.append(cnt)

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)
#        if j in plist:
#            cnt +=1
    ans=pcnt[tr-1]-pcnt[tl-1]
#    print(tr, pcnt[tr])
#    print(tl, pcnt[tl])
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
max_p = 10 ** 5

p = [0] * (max_p + 1)
p[0] = 1
p[1] = 1

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

a = [0] * (max_p + 1)
for i in range(1, max_p + 1):
    if (p[i] is 0) and (p[(i + 1) // 2] is 0):
        a[i] = a[i - 1] + 1
    else:
        a[i] = a[i - 1]

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())

    print(a[R] - a[L - 1])

Submission status: Wrong Answer

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, 10000 + 1):
        primes.append(is_prime(i))

    results = [0]
    for i in xrange(1, 10000 + 1):
        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: Wrong Answer

Solution code:
Q = int(input())
n = 2 
num = [0]*(100001)
num[0] = -1
num[1] = 1
ans = 0
A = []
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(n,m)
    A.append(ans)
for a in range(len(A)):
    print(A[a])

Submission status: Wrong Answer

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(1, 10000 + 1):
        primes.append(is_prime(i))

    results = [0]
    for i in xrange(1, 10000 + 1):
        if primes[i - 1] and primes[(i + 1) / 2 - 1]:
            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: Wrong Answer

Solution code:
li = [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]

q = int(input())

for i in range(q):
	ans = 0
	a, b = map(int,input().split())
	for w in range(35):
		if a <= li[w] and li[w] <= b:
			ans = ans+1
	print(ans)

Submission status: Wrong Answer

Solution code:
import math
def isPrime(n):
    if n==1:
        return(False)
    if n==2:
        return(True)
    for i in range(2,int(math.sqrt(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: Wrong Answer

Solution code:
def prime(n):
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return [i for i in range(2,n) 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 < LR[i][1]:
    max = LR[i][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: Wrong Answer

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

max_p = 10 ** 5

p = [0] * (max_p + 1)
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 + 1) // x):
            p[n * x] = 1

a = [0] * (max_p + 1)
for i in range(1, max_p + 1):
    if (p[i] is 0) and (p[(i + 1) // 2] is 0):
        a[i] = a[i - 1] + 1
    else:
        a[i] = a[i - 1]

Q = int(input())

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

    print(a[r] - a[l - 1])

Submission status: Wrong Answer

Solution code:
li = [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]

q = int(input())

for i in range(q):
	ans = 0
	a, b = map(int,input().split())
	for w in range(34):
		if a <= li[w] and li[w] <= b:
			ans = ans+1
	print(ans)

Submission status: Wrong Answer

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

max_p = 10 ** 5

p = [0] * (max_p + 1)
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

a = [0] * (max_p + 1)
for i in range(1, max_p + 1):
    if (p[i] is 0) and (p[(i + 1) // 2] is 0):
        a[i] = a[i - 1] + 1
    else:
        a[i] = a[i - 1]

Q = int(input())

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

    if l > 3:
        print(a[r] - a[l - 2])
    else:
        print(a[r])

Submission status: Wrong Answer

Solution code:
li = [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]

q = int(input())

for i in range(q):
	ans = 0
	a, b = map(int,input().split())
	for w in range(34):
		if a <= li[w] and li[w] <= b:
			ans = ans+1
	print(ans)

Submission status: Wrong Answer

Solution code:
import re
import math
num = int(input())
sosuu = [2]
max = 100001
for i in range(3,max,2):
    flag = 1
    flag2 = 0
    for j in sosuu:
        if(j > math.sqrt(i)):
            flag2 += 1
        if(flag2>2):
            break
        if(i % j == 0):
            flag = 0
            break
    if(flag):
        sosuu.append(i)
# print(len(sosuu))
binsosuu = [0 for a in range(max)]
binbinsosuu = [0 for a in range(max)]
sumsosuu = [0 for a in range(max)]
butu = []
for i in sosuu:
    binsosuu[i] = 1
for i in range(1,max,2):
    if(binsosuu[i] + binsosuu[int((i+1)/2)] == 2):
        binbinsosuu[i] = 1
        # print(i)
        butu.append(i)
for i in range(max):
    sumsosuu[i] = sumsosuu[i-1] + binbinsosuu[i]
# print(butu)
# print(binsosuu)
# print(binbinsosuu)
# print(sumsosuu)
# print(sumsosuu[51])
# print(sumsosuu[19])
for i in range(num):
    x,y = map(int,input().split(" "))
    # print("---",sumsosuu[y],sumsosuu[x])
    if(x==y):
        if(binbinsosuu[x]==1):
            print(1)
        else:
            print(0)
    else:
        # if(sumsosuu[y]-sumsosuu[x] == 0 and sumsosuu[x]>0):
        #     print(1)
        # else:
        print(sumsosuu[y]-sumsosuu[x]+binbinsosuu[y]+binbinsosuu[x])

Submission status: Wrong Answer

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

max_p = 10 ** 5

p = [0] * (max_p+1)
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

a = [0] * (max_p+1)
for i in range(1, max_p+1):
    if (p[i] is 0) and (p[(i + 1) // 2] is 0):
        a[i] = a[i - 1] + 1
    else:
        a[i] = a[i - 1]

Q = int(input())

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

    print(a[r] - a[l - 1])

Submission status: Wrong Answer

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

a = [0] * max_p
for i in range(1, max_p):
    if (p[i] is 0) and (p[(i + 1) // 2] is 0):
        a[i] = a[i - 1] + 1
    else:
        a[i] = a[i - 1]

Q = int(input())

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

    print(a[r] - a[l - 1])

Submission status: Wrong Answer

Solution code:
def isPrime(n):
    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: Wrong Answer

Solution code:
Q = int(input())


M = 10**5 + 5
primes = [True] * M
primes[0] = False
primes[1] = False


for i in range(2, M):
    if primes[i]:
        for j in range(2, M//i):
            primes[i*j] = False

cnt = [0] * M

for i in range(3, M):
    cnt[i] = cnt[i-1]
    if primes[i] and primes[(i+1)//2]:
        cnt[i] += 1

queues = []
for q in range(Q):
    l, r = map(int, input().split())
    queues.append((l, r))

for l, r in queues:
    print(cnt[r] - cnt[l-1])

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
Q = int(input())


M = 10**5 + 5
primes = [True] * M
primes[0] = False
primes[1] = False


for i in range(2, M):
    if primes[i]:
        for j in range(2, M//i):
            primes[i*j] = False

cnt = [0] * M

for i in range(3, M):
    cnt[i] = cnt[i-1]
    if primes[i] and primes[(i+1)//2]:
        cnt[i] += 1

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

Submission status: Wrong Answer

Solution code:
q = int(input())


que = []
for i in range(q):
    r = input()
    que.append(r)

def prime(n):
    half = int(n+1 / 2)
    for i in range(n-1):
        if n % (i+1) == 0:
            return(False)
    return(True)



for i in range(len(que)):
    count = 0
    a = int(que[i].split(" ")[0])
    b = int(que[i].split(" ")[1])
    c = min(a, b)
    for i in range(abs(a-b)+1):
        if not(prime(c + i)):
            if (c + i + 1)/2 == float(int((c + i + 1)/2)):
                if not(prime(int((c+i+1)/2))):
                    count += 1
    print(count)

Submission status: Wrong Answer

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  int((i+1)/2) in plist:
            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: Wrong Answer

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(l):
            if is_prime((l+1)/2):
                count += 1
    print count

Submission status: Wrong Answer

Solution code:
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 x & 1:
                if 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: Wrong Answer

Solution code:
import math
def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    for i in xrange(3, int(math.sqrt(n))+1, 2):
        if n%i == 0:
            return False
    return True

m = [(lambda x: True if is_prime(i) and is_prime((i+1)/2) else False)(i) for i in xrange(10**5)]
print m
n = input()
for _ in xrange(n):
    s = 0
    a, b = map(int, raw_input().split())
    for i in xrange(a, b+1):
        if m[i]:
            s += 1
    print s

Submission status: Wrong Answer

Solution code:
import math

MAXN = 100001
isPrime = [True for x in range(0, MAXN)]

def findPrime():
    isPrime[1] = False
    for i in range(2, MAXN):
        if isPrime[i]:
            for j in range(i + i, int(math.sqrt(MAXN)) + 1, i):
                isPrime[j] = False

findPrime()

cache = [0 for x in range(0, MAXN)]

pSum = 0
for i in range(1, MAXN, 2):
    cache[i] = pSum
    if isPrime[i] and isPrime[(i+1)//2]:
        cache[i] += 1
    pSum = cache[i]

Q = int(input())

for i in range(Q):
    l, r = map(int, input().split())
    if l == r:
        print(cache[r] - cache[r-2])
    else:
        print(cache[r] - cache[l - 2])

Submission status: Wrong Answer

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:
    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

for i in range(n):
  a,b=[int(i) for i in input().split()]
  x=0
  for j in range(a,b+1,2):
    x+=sosu(j)*sosu((j+1)/2)
  print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
def generate_is_prime_sieve(N):
    is_prime = [True] * (N + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= N:
        if is_prime[p]:
            for n in range(p * p, N + 1, p):
                is_prime[n] = False
        p += 1
    return is_prime
list = generate_is_prime_sieve(10**5)

for test in range(int(sys.stdin.readline())):
    a, b = map(int, sys.stdin.readline().split())
    count = 0
    for x in range(a, b + 1,2):
        if list[x]:
            if list[(x + 1) // 2]:
                count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
def generate_is_prime_sieve(N):
    is_prime = [True]*(N+1)
    is_prime[0] = is_prime[1] = False
    for p in range(2,N+1):
        if is_prime[p]:
            for n in range(2*p,N+1,p):
                is_prime[n] = False
    return is_prime
list = generate_is_prime_sieve(10**5)

for test in range(int(sys.stdin.readline())):
    a, b = map(int, sys.stdin.readline().split())
    count = 0
    for x in range(a, b + 1,2):
        if list[x]:
            if list[(x + 1) // 2]:
                count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
def generate_is_prime_sieve(N):
    is_prime = [True]*(N+1)
    is_prime[0] = is_prime[1] = False
    for p in range(2,N+1):
        if is_prime[p]:
            for n in range(2*p,N+1,p):
                is_prime[n] = False
    return is_prime
list = generate_is_prime_sieve(10**5)

for test in range(int(sys.stdin.readline())):
    a, b = map(int, sys.stdin.readline().split())
    count = 0
    for x in range(a, b + 1):
        if list[x]:
            if list[(x + 1) // 2]:
                count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
dp=[1]*(10**5+1)
dp[0],dp[1]=0,0
for i in range(2,10**5+1):
  if dp[i]==0:
    continue
  j=i
  while j+i<=10**5:
    j+=i
    if dp[j]==1:
      dp[j]-=1
ni=[0]*(10**5+1)
for i in range(2,10**5+1):
  if dp[i]==1 and dp[(i+1)//2]==1:
    ni[i]=1

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

Submission status: Time Limit Exceeded

Solution code:
import math

q = int(input())
lr = list(list(map(int, input().split())) for _ in range(q))

#print(lr)

l = []
for i in range(q):
    l.append(lr[i][0])

r = []
for i in range(q):
    r.append(lr[i][1])

#print(l, r)

def is_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

for i in range(q):
    num = 0
    for j in range(l[i], r[i] + 1, 2):
        if is_prime(j) == True and is_prime((j + 1) // 2) == True:
            num += 1
    print(num)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
l = [0 for q in range(Q)]
r = [0 for q in range(Q)]
for q in range(Q):
  l[q], r[q] = map(int, input().split(' '))
max_r = max(r)
prime_numbers = [True for n in range(max_r+1)]
similar_numbers = [False for n in range(max_r+1)]

prime_numbers[0], prime_numbers[1] = False, False    # 1 is not a prime number
for divisor in range(2, max_r//2 + 1):
  if prime_numbers[divisor]:
    for multipler in range(2, max_r//divisor + 1):
      prime_numbers[divisor * multipler] = False
      
for N in range(1, max_r + 1, 2):
  if prime_numbers[N] and prime_numbers[(N+1)//2]:
    similar_numbers[N] = True
    
for q in range(Q):
  print(sum(similar_numbers[l[q]:r[q]+1]))

Submission status: Time Limit Exceeded

Solution code:
MAX=10**5+1
is_prime=[True]*MAX
is_prime[0]=False
is_prime[1]=False
for i in range(2,MAX):
  if is_prime[i]==False:
    continue
  for j in range(i*2,MAX,i):
    is_prime[j]=False

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bsl

def main():
    with open(0) as f:
        Q = int(f.readline())
        Query = [tuple(map(int, line.split())) for line in f.readlines()]
    
    p_table = makePtable(10**5)
    p_set = set(p_table)
    Like2017 = [p for p in p_table if (p+1)//2 in p_set]
    database = [bsl(Like2017, i) for i in range(1,10**5+1)]

    for l,r in Query:
        print(database[r] - database[l-1])

def makePtable(N):
    table = list(range(2,N+1))
    result = []
    while len(table) != 0:
        p = table[0]
        result.append(p)
        table = [x for x in table[1:] if x % p != 0]
    return result

main()

Submission status: Time Limit Exceeded

Solution code:
q=int(input())

#prime table
prime=[0 for i in range(10**5+5)]
for i in range(2,10**5+5):
  j=1
  if not prime[i]:
    while j*i<=10**5+4:
      prime[j*i]=i
      j+=1

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

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
n = 10**5
nums = [False]*2+[True]*(n-2)

for i in range(2, n):
    if nums[i]:
        for j in range(i*2, n, i):
            nums[j] = False
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())
    for i in range(l, r+1, 2):
        if nums[i] == nums[(i+1)//2] == True:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime_num(n):
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            return False
    return True

N = int(input())
for _ in range(N):
    nmin, nmax = map(int, input().split())
    if nmin < 2:
        nmin = 3
    ans = 0
    for i in range(nmin, nmax+1, 2):
        judge1 = prime_num(i)
        if judge1:
            i = (i+1)/2
            judge2 = prime_num(i)
            if judge2:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

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

a = [0]*10**5
prime = isPrime_np(10**5)
pset = set(prime)
for p in prime:
    if (p+1)/2 in pset:
        a[p] = 1

ans = []
for l,r in lr:        
    ans.append(sum(a[l:r+1]))

print(*ans,sep="\n")