Problem:


Score : 400 points

Problem Statement

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

You are given Q queries.

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

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

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

Sample Input 1

1
3 7

Sample Output 1

2

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

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

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

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

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

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

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Time Limit Exceeded

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

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

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


C = []
for i in range(q):
  ran = list(map(int, input().split()))
  for i in range(q):
    if ran[0] % 2 == 0:
        j = ran[0]+1
    j = ran[0]
    count = 0
    while j <= ran[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:
#coding:utf-8
'''
pp = [341,561,645,1105,1387,1729,1905,2047,2465,2701,
               2821,3277,4033,4369,4371,4681,5461,6601,7957,8321,
               8481,8911]
'''
def is_prime(q):
    p = int(abs(q))
    if p == 2: return True
    if p < 2 or p&1 == 0: return False
#    for k in pp:
#        if q == k:
#            return False
    return pow(2, p-1, p) == 1

q = int(input())
e = [[int(i) for i in input().split()] for i in range(q)]

ct = 0

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

Submission status: Time Limit Exceeded

Solution code:
sosuu = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
         67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
         139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
         223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
         293, 307, 311, 313]


def sosuu_hantei(candidate):
    if candidate == 1:
        return False
    for i in sosuu:
        if candidate <= i:
            return True
        if candidate % i == 0:
            return False
    return True


def main():
    separator = ' '
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split(sep=separator))
        counter = 0
        for candidate in range(l, r+1, 2):
            if sosuu_hantei(candidate) and sosuu_hantei(int((candidate+1)/2)):
                counter += 1
        print(counter)


if __name__ == "__main__":
    main()

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

for i in range(q):
    tl, tr = map(int,input().split(' '))
    cnt=0
    for j in range(tl,tr+1):
        if is_prime_trial_division(j):
            nj = int((j+1)/2)
            if is_prime_trial_division(nj):
                cnt +=1
    print(cnt)

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

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

for i in range(q):
    cnt = 0
    l, r = [int(j) for j in input().split()]
    for j in range(l, r + 1):
        if (j in primes) and ((int((j+1)/2)) in primes):
            cnt += 1
    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 = int(input())
alst = []

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