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:
# Python program to print all primes smaller than or equal to 
# n using Sieve of Eratosthenes 
  
def SieveOfEratosthenes(n):
    # copy pasted from https://www.geeksforgeeks.org/sieve-of-eratosthenes/
      
    # Create a boolean array "prime[0..n]" and initialize 
    #  all entries it as true. A value in prime[i] will 
    # finally be false if i is Not a prime, else true. 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
          
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True): 
              
            # Update all multiples of p 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
      
    # Print all prime numbers 
    ans = []
    for p in range(2, n): 
        if prime[p]: 
            ans.append(p)
    return ans

def binarySearch (arr, l, r, x): 
    # from https://www.geeksforgeeks.org/python-program-for-binary-search/
    # Check base case 
    if r >= l: 
  
        mid = int(l + (r - l)/2)
  
        # If element is present at the middle itself 
        if arr[mid] == x: 
            return True 
          
        # If element is smaller than mid, then it can only 
        # be present in left subarray 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
  
        # Else the element can only be present in right subarray 
        else: 
            return binarySearch(arr, mid+1, r, x) 
  
    else: 
        # Element is not present in the array 
        return False
  
# Test array 

primes = SieveOfEratosthenes(10**5+9)
sheet = []
for x in range(1, 10**5+9):
  sheet.append(binarySearch(primes, 0, len(primes)-1, x) and binarySearch(primes, 0, len(primes)-1, (x+1)/2))


queries = int(input())
ans = []
for j in range(queries):
  a,b = [int(x) for x in input().split()]
  ans.append(sheet[a-1:b].count(True))
for x in ans:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
# Python program to print all primes smaller than or equal to 
# n using Sieve of Eratosthenes 
  
def SieveOfEratosthenes(n):
    # copy pasted from https://www.geeksforgeeks.org/sieve-of-eratosthenes/
      
    # Create a boolean array "prime[0..n]" and initialize 
    #  all entries it as true. A value in prime[i] will 
    # finally be false if i is Not a prime, else true. 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
          
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True): 
              
            # Update all multiples of p 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
      
    # Print all prime numbers 
    ans = []
    for p in range(2, n): 
        if prime[p]: 
            ans.append(p)
    return ans

def binarySearch (arr, l, r, x): 
    # from https://www.geeksforgeeks.org/python-program-for-binary-search/
    # Check base case 
    if r >= l: 
  
        mid = int(l + (r - l)/2)
  
        # If element is present at the middle itself 
        if arr[mid] == x: 
            return True 
          
        # If element is smaller than mid, then it can only 
        # be present in left subarray 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
  
        # Else the element can only be present in right subarray 
        else: 
            return binarySearch(arr, mid+1, r, x) 
  
    else: 
        # Element is not present in the array 
        return False
  
# Test array 

primes = SieveOfEratosthenes(10**5+9)

queries = int(input())
for j in range(queries):
  a,b = [int(x) for x in input().split()]
  ans = 0
  for x in range(a,b+1, 2):
    if binarySearch(primes, 0, len(primes)-1, x) and binarySearch(primes, 0, len(primes)-1, (x+1)/2):
      ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Python program to print all primes smaller than or equal to 
# n using Sieve of Eratosthenes 
  
def SieveOfEratosthenes(n):
    # copy pasted from https://www.geeksforgeeks.org/sieve-of-eratosthenes/
      
    # Create a boolean array "prime[0..n]" and initialize 
    #  all entries it as true. A value in prime[i] will 
    # finally be false if i is Not a prime, else true. 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
          
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True): 
              
            # Update all multiples of p 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
      
    # Print all prime numbers 
    ans = []
    for p in range(2, n): 
        if prime[p]: 
            ans.append(p)
    return ans

def binarySearch (arr, l, r, x): 
    # from https://www.geeksforgeeks.org/python-program-for-binary-search/
    # Check base case 
    if r >= l: 
  
        mid = int(l + (r - l)/2)
  
        # If element is present at the middle itself 
        if arr[mid] == x: 
            return True 
          
        # If element is smaller than mid, then it can only 
        # be present in left subarray 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
  
        # Else the element can only be present in right subarray 
        else: 
            return binarySearch(arr, mid+1, r, x) 
  
    else: 
        # Element is not present in the array 
        return False
  
# Test array 

primes = SieveOfEratosthenes(10**5+9)

queries = int(input())
for j in range(queries):
  a,b = [int(x) for x in input().split()]
  ans = 0
  for x in range(a,b+1):
    if binarySearch(primes, 0, len(primes)-1, x) and binarySearch(primes, 0, len(primes)-1, (x+1)/2):
      ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def searchPrimeNumber(N):
    N = N + 1
    is_prime = np.ones((N,), dtype=bool)
    is_prime[:2] = 0
    N_max = int(np.sqrt(N))
    for j in range(2, N_max+1):
        if (is_prime[j]):
            is_prime[j*j::j] = False
    prime = np.arange(N)[is_prime]
    return prime


def main():
    Q = int(readline())
    m = map(int, read().split())
    LR = list(zip(m, m))
    # 事前に10**5までにある2017に似た素数リストを作る
    A = searchPrimeNumber(10**5)

    like_2017 = np.zeros(10**5 + 1, dtype=bool)
    for a in A:
        if (a + 1) / 2 in A:
            like_2017[a] = True

    B = np.arange(10**5+1)[like_2017]
    for l, r in LR:
        C = B[B <= r]
        print(len(C[l <= C]))
        


main()

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
def solve(num):
    ans = pow(2, num-1, num)
    ANS = pow(2, (num+1)//2 -1, (num+1)//2)
    if num == 2:
        ans = 1
    if (num+1)//2 == 2:
        ANS = 1
    if num < 2:
        ans = 10**9
    if ans == 1 and ANS == 1:
        return 1
    else:
        return 0
dt = [list(map(int, input().split())) for _ in range(q)]
for i in range(q):
    l, r = dt[i]
    c = 0
    while l <= r:
        c += solve(l)
        l += 2
    print(c)

Submission status: Time Limit Exceeded

Solution code:
# 全てを先に計算しておき、累積和を使って結果を表示する。
# それにより、同じ計算を何度もしなくてすむ。最大10^5になるはず。

import math

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

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

    return True


# 2017に似た数

def is_like2017(n):
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False


Q = int(input())

l_list = [0]*Q
r_list = [0]*Q

for i in range(Q):
    l_list[i], r_list[i] = map(int, input().split())
    
min_value = min(l_list)
max_value = max(r_list)

ans = []

for i in range(min_value, max_value+1):
    if i % 2 == 0:
        ans.append(0)
    elif is_prime(i) and is_like2017(i):
        ans.append(1)
    else:
        ans.append(0)

        
for i in range(Q):
    print(sum(ans[l_list[i]-min_value:r_list[i]-min_value+1]))

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

# 素数判定
import math

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

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

    return True


# 2017に似た数

def is_like2017(n):
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False


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