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


class Primes:
    def __init__(self):
        self.primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 33]

    def isprime(self, x):
        if x < self.primes[-1]:
            return x in self.primes
        
        self.extend(math.ceil(math.sqrt(x)))
        for p in self.primes:
            d, m = divmod(x, p)
            if m == 0:
                return False
        return True

    def extend(self, end):
        start = self.primes[-1]
        for i in range(start, end+2, 2):
            if self.isprime(i):
                self.primes.append(i)


    def count2017like(self, start, end):
        count = 0
        for i in range(start, end+2, 2):
            if self.isprime(i) and self.isprime((i+1)//2):
                count += 1
        return count



if __name__ == "__main__":
    q = int(input())
    xs = [list(map(int, input().split())) for i in range(q)]

    p = Primes()
    for start, end in xs:
        print(p.count2017like(start, end))

Submission status: Time Limit Exceeded

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

import random
import sys

def is_prime(n, k=50):
    assert n > 0
    if n == 2:
        return True
    elif n == 1 or n % 2 == 0:
        return False
    # n - 1を2 ^ s * dの形にする
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for i in range(k):
        a = random.randint(1, n - 1)
        if pow(a, d, n) != 1:
            for r in range(0, s):
                if pow(a, d * 2 ** r, n) == n - 1:
                    break
            else:
                return False
    return True

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

for c in childs:
    count = 0
    for n in range(c[0], c[1]+1):
        if is_prime(n) and is_prime((n+1)//2):
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
def sieve_of_erastosthenes(num):
    input_list = [0 if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else 1 for i in range(num)]
    input_list[0] = input_list[1] = 0
    input_list[2] = input_list[3] = input_list[5] = 1
    sqrt = math.sqrt(num)
    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = 0

q = int(input())
l_list = []
r_list = []
for i in range(q):
    l, r = map(int, input().split())
    l_list.append(l)
    r_list.append(r)
minval = min(l_list)
maxval = max(r_list)
sieve = sieve_of_erastosthenes(maxval+1)
def is_prime(x):
    # print(x)
    return sieve[x]
def is_like2017(x):
    return is_prime(x) * is_prime(int((x+1)/2))
like2017 = list(range(maxval+1))
for i in like2017:
    like2017[i] = is_like2017(i)
for l, r in zip(l_list, r_list):
    print(sum(like2017[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import pdb
#import Eratosthenes as Erato

def main():
    Q = int(raw_input())
    Ls = np.zeros(Q).astype(int)
    Rs = np.zeros(Q).astype(int)
    for k in range(Q):
        LR = raw_input().split(' ')
        Ls[k] = int(LR[0]) - 1
        Rs[k] = int(LR[1])

    for k in range(Q):
        print specialnumbers(Rs[k]) - specialnumbers(Ls[k])


def specialnumbers(ell):
    primeuptoell = np.array(sieve(ell))
    shiftvalue = (primeuptoell + 1)/2
    intersect = set(primeuptoell).intersection(set(shiftvalue))
    return len(intersect)


def sieve(number):
    sourcelist = np.array(range(2, number + 1))
    primelist = [2]
    primefront = primelist[0]
    while primefront < np.sqrt(number):
        sourcelist = sourcelist[np.where(np.mod(sourcelist, primefront) != 0)[0]]
        primelist += [sourcelist[0]]
        primefront = primelist[len(primelist)-1]

    return primelist + sourcelist[1:len(sourcelist)].tolist()



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
Q_SIZE = math.pow(10,5) 
Q = int(input())

Check_Prime = [-1 for i in range(int(Q_SIZE))]
Count_like = [0 for i in range(int(Q_SIZE//2))]

C_Range_L = 0 
C_Range_R = 0

def check_range(L,R):
    for i in range(L,R+1,2):
        if(Check_Prime[i] < 0):
            if isprime(i):
                Check_Prime[i] = 1
                n = int((i+1)/2)
                if(Check_Prime[n] < 0):
                    if(isprime(n)) : 
                        Count_like[i//2] = 1
                elif(Check_Prime[n] == 1):
                    Count_like[i//2] = 1
            else:
                Check_Prime[i] = 0
                
        elif(Check_Prime[i] == 1):
            n = int((i+1)/2)
            if(Check_Prime[n] < 0):
                if(isprime(n)) : 
                    Count_like[i//2] = 1
            elif(Check_Prime[n] == 1):
                Count_like[i//2] = 1

def isprime(n): 
    if n < 2 : return False 
    if n == 2 : return True 
    if n % 2 == 0 : return False

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

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

    if(C_Range_L == 0 and C_Range_R == 0):
        check_range(l,r)
        C_Range_L = l
        C_Range_R = r

    if(C_Range_L > l):
        check_range(l,C_Range_L)
        C_Range_L = l

    if(r > C_Range_R):
        check_range(C_Range_R,r)
        C_Range_R = r

    print(sum(Count_like[l//2:r//2+1]))

Submission status: Time Limit Exceeded

Solution code:
import math
Q_SIZE = math.pow(10,5) 
Q = int(input())

Count_Prime = [False for i in range(int(Q_SIZE//2))] 
C_Range_L = 0 
C_Range_R = 0

def check_range(L,R):
    for i in range(L,R+1,2): 
        if(isprime(i) and isprime((i+1)/2)): 
            Count_Prime[i//2] = 1


def isprime(n): 
    if n < 2 : return False 
    if n == 2 : return True 
    if n % 2 == 0 : return False

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

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

    if(C_Range_L == 0 and C_Range_R == 0):
        check_range(l,r+1)
        C_Range_L = l
        C_Range_R = r

    if(C_Range_L > l):
        check_range(l,C_Range_L+1)
        C_Range_L = l

    if(r > C_Range_R):
        check_range(C_Range_R,r+1)
        C_Range_R = r

    print(sum(Count_Prime[l//2:r//2+1]))

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
def isPrime(num):
    a = 2
    if num == 1:
        return False

    while num >= a*a:
        if num%a == 0:
            return False
        a += 1

    return True

if __name__ == '__main__':
    q = int(input())
    a = []
    b = {}
    minNum, maxNum = (float('inf'), float('-inf'))
    for tmp in range(q):
        l, r = map(int, input().split())
        minNum = min(minNum, l)
        maxNum = max(maxNum, r)
        a.append((l,r))

    for tmp in range(minNum, maxNum+1):
        factor = (tmp+1)/2
        if isPrime(tmp) and factor == int(factor) and isPrime(factor):
            b[tmp] = 1
        else:
            b[tmp] = 0

    for tmp in a:
        ans = 0
        for tmp2 in range(tmp[0], tmp[1]+1):
            if b[tmp2] == 1:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
maxn = 100000 + 3
prime = [True for i in range(maxn)]
prime[0] = False
prime[1] = False
for i in range(maxn):
    if prime[i]:
        j = i+i
        while j < maxn:
            prime[j] = False
            j += i
n = int(input())
for i in range(n):
    l, r = map(int, input().split())
    c = 0
    for j in range(l, r+1):
        if prime[j] and prime[(j+1)//2]:
            c += 1 
    print(c)

Submission status: Time Limit Exceeded

Solution code:
def isprime(z):
    if z < 2:return False
    if z == 2:return True
    i = 2
    while i*i <= z:
        if z % i == 0:
            return False
        i+=1
    return True
n = int(input())
for i in range(n):
    l, r = map(int, input().split())
    c = 0
    for j in range(l, r+1):
        if isprime(j) and isprime((j+1)/2):
            c+=1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import math

def isPrime(num):
    if num < 2:
        return False
    else:
        rootNum = math.floor(math.sqrt(num))
        for i in range(2,rootNum+1):
            if num % i == 0:
                return False
    return True

def solve():
    lst = []
    count = int(input())
    for i in range(count):
        ans = 0
        l, r = map(int, input().split())
        k = l
        while k <= r:
            if isPrime(k) and isPrime((k+1)/2):
                ans += 1
            k += 2
        lst.append(str(ans))
    print('\n'.join(lst))
solve()

Submission status: Time Limit Exceeded

Solution code:
import math

def isPrime(num):
    if num < 2:
        return False
    else:
        rootNum = math.floor(math.sqrt(num))
        for i in range(2,rootNum+1):
            if num % i == 0:
                return False
    return True

def solve():
    lst = []
    count = int(input())
    for i in range(count):
        ans = 0
        l, r = map(int, input().split())
        for k in range(l,r+1):
            if isPrime(k) and isPrime((k+1)/2):
                ans += 1
        lst.append(str(ans))
    print('\n'.join(lst))
solve()

Submission status: Time Limit Exceeded

Solution code:
import math

def isPrimeNumber(num):
    isPrimeNum = True
    for i in range(2,math.floor(math.sqrt(num)) + 1):
        if num % i == 0:
            isPrimeNum = False

    if num == 1:
        isPrimeNum = False

    return isPrimeNum

def is2017alikeNum(num):
    is2017alikeNum = False
    alikeNum = (num + 1) / 2
    if isPrimeNumber(num) and isPrimeNumber(alikeNum):
        is2017alikeNum = True
    return is2017alikeNum


N = int(input())
inputList = []
for count in range(0,N):
    l,r = map(int, input().split())
    tempList = [l,r]
    inputList.append(tempList)

for i in range(0,N):
    l = inputList[i][0]
    r = inputList[i][1]

    count = 0
    for j in range(l, r + 2 , 2):
        if is2017alikeNum(j):
            count += 1

    print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

# AtCoder Beginner Contest 084
# D: 2017-like Number

import sys, math

MAX_N = 100000
isprime_ = []

def sieve():
  global isprime_, MAX_N
  isprime_ = [i >= 2 for i in range(0, MAX_N + 1)]
  for p in range(2, MAX_N + 1):
    if isprime_[p]:
      for q in range(p + p, MAX_N + 1, p):
        isprime_[q] = False

def isPrime(n):
  global isprime_
  return isprime_[n]

def is2017like(n):
  return isPrime(n) and isPrime((n + 1) // 2)

# the number of 2017-like numbers between l and r.
def solve(l, r):
  return len([i for i in range(l, r + 1, 2) if is2017like(i)])

sieve()
Q = int(sys.stdin.readline())
for i in range(Q):
  l, r = [int(w) for w in sys.stdin.readline().split()]
  print(solve(l, r))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

# AtCoder Beginner Contest 084
# D: 2017-like Number

import sys, math

def isPrime(n):
  if n <= 2: return n == 2
  if n % 2 == 0: return False
  maxd = int(math.sqrt(n))
  for d in range(3, maxd + 1, 2):
    if n % d == 0: return False
  return True

def is2017like(n):
  return isPrime(n) and isPrime((n + 1) // 2)

# the number of 2017-like numbers between l and r.
def solve(l, r):
  return len([i for i in range(l, r + 1, 2) if is2017like(i)])

Q = int(sys.stdin.readline())
for i in range(Q):
  l, r = [int(w) for w in sys.stdin.readline().split()]
  print(solve(l, r))

Submission status: Time Limit Exceeded

Solution code:
prime=[0]*100001
prime[0]=1
prime[1]=1
for i in range(0,100001):
  if prime[i]==0:
    cnt=2
    while cnt*i<100001:
      prime[cnt*i]=1
      cnt+=1

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

Submission status: Time Limit Exceeded

Solution code:
def isPrime(num):
	if num <=1:
		return False

	elif num == 2 or num == 3:
		return True

	elif num % 2 == 0:
		return False

	else:
		i = 3

		while num >= i ** 2:
			if num % i != 0:
				i += 2
				continue

			else:
				return False
		return True




if __name__ == '__main__':

	Q = int(input())

	for i in range(Q):
		a, b = input().split()
		a, b = int(a), int(b)
		count = 0

		for i in range(a, b + 1, 2):
			if isPrime(i) and isPrime((i + 1)/2):
				count += 1
		print(count)

Submission status: Time Limit Exceeded

Solution code:
def isPrime(num):
	if num <=1:
		return False

	elif num == 2 or num == 3:
		return True

	elif num % 2 == 0:
		return False

	else:
		i = 3

		while True:
			if num % i != 0:
				i += 2

				if i ** 2 > num:
					return True

				else:
					continue

			else:
				return False




if __name__ == '__main__':
	Q = int(input())

	for i in range(Q):
		a, b = input().split()
		a, b = int(a), int(b)
		count = 0

		for i in range(a, b + 1, 2):
			if isPrime(i) and isPrime((i + 1)/2):
				count += 1
		print(count)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, sqrt

Q = int(input())
querys = [tuple(map(int, input().split())) for i in range(Q)]

N = max(map(max, querys))

Primes = [False] * 2 + [True] * (N - 1)
for i in range(3, N + 1):
    for j in range(2, ceil(sqrt(i)) + 1):
        if i % j == 0:
            Primes[i] = False

s2017s = [False] * (N + 1)
for i in range(1, N + 1, 2):
    if Primes[i] and Primes[(i + 1) // 2]:
        s2017s[i] = True

nums = [0] * (N + 1)
for i in range(1, N + 1, 2):
    nums[i] = nums[i - 2]
    if s2017s[i]:
        nums[i] += 1

for li, ri in querys:
    print(nums[ri] - nums[max(0, li - 2)])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

prime = [True] * 100001
like2017 = [False] * 100001
for i in range(2, 100001):
  if prime[i]:
    for j in range(i*2, 100001, i):
      prime[j] = False
    if i != 2 and prime[(i+1)//2]:
      like2017[i] = True

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

Submission status: Time Limit Exceeded

Solution code:
import math

# def primes(x):
#     if x < 2: return []

#     primes = [i for i in range(x)]
#     primes[1] = 0 # 1は素数ではない
#     x_sqrt = math.sqrt(x) # 記憶させていちいち計算しない

#     # エラトステネスのふるい
#     for prime in primes:
#         if prime == 0:
#             continue # 先に処理
#         if prime > x_sqrt: 
#             break
#         for non_prime in range(2 * prime, x, prime):
#             primes[non_prime] = 0

#     return [prime for prime in primes if prime != 0]
def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False
                
q = int(input())
l_list = []
r_list = []
for _ in range(q):
    l, r = list(map(int,input().split()))
    l_list.append(l)
    r_list.append(r)
    
maxr = max(r_list)
p_list = list(primes_sieve2(maxr+1))

sim_list = []
for p in p_list:
    if (p+1)/2 in p_list:
        sim_list.append(p)
        
cumulation = [0 for _ in range(maxr+1)]
for s in sim_list:
    cumulation[s] = 1

for i in range(1,len(cumulation)):
    cumulation[i] += cumulation[i-1]

for i in range(q):
    print(cumulation[r_list[i]]-cumulation[l_list[i]-1])

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_I(): return map(int, stdin)
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))

##### main #####

def is_prime(n):
    i=2
    while i*i <= n:
        if n%i == 0:
            return False
        i+=1
    return n != 1


def main():
	n = I()
	memo = {}
	for i in range(n):
		l,r = LI()
		x=0
		for j in range(l,r+1,2):
			if j in memo:
				if memo[j] == True:
					x+=1
			else:
				jj = (j+1)/2
				if is_prime(j) and is_prime(jj):
					memo[j] = True
					x+=1
				else:
					memo[j] = False
		print(x)



if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# D - 2017-like Number
# coding: utf-8
import math

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

#---------------------------------

max_num = max(r)

#primes:素数のリスト
nums = [i+1 for i in range(max_num)]
nums.remove(1)
primes = [0]

while nums[0] * nums[0] <= max_num:
  prime_now = nums[0]
  primes.append(prime_now)
  for i in nums:
    if i % prime_now == 0: nums.remove(i)
primes.remove(0)
primes += nums

#primes_2017:2017に似た素数のリスト
primes_2017 = [0]
for i in primes:
  if i != 2 and ((i+1)/2 in primes) : primes_2017.append(i)
primes_2017.remove(0)

#---------------------------------

result = [0]
for i in range(Q):
  result.append(sum(x>=l[i] and x<=r[i] for x in primes_2017))
result.remove(0)

for i in result: print i

Submission status: Time Limit Exceeded

Solution code:
# D - 2017-like Number
# coding: utf-8
import math

#---------------------------------

max_num = 100000

#primes:素数のリスト
nums = [i+1 for i in range(max_num)]
nums.remove(1)
primes = [0]

while nums[0] * nums[0] <= max_num:
  prime_now = nums[0]
  primes.append(prime_now)
  for i in nums:
    if i % prime_now == 0: nums.remove(i)
primes.remove(0)
primes += nums

#primes_2017:2017に似た素数のリスト
primes_2017 = [0]
for i in primes:
  if i != 2 and ((i+1)/2 in primes) : primes_2017.append(i)
primes_2017.remove(0)

#---------------------------------

result = [0]
Q = int(raw_input())
for i in range(Q):
  l, r = map(int, raw_input().split())
  result.append(sum(x>=l and x<=r for x in primes_2017))
result.remove(0)

for i in result: print i

Submission status: Time Limit Exceeded

Solution code:
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない
    x_sqrt = math.sqrt(x) # 記憶させていちいち計算しない

    # エラトステネスのふるい
    for prime in primes:
        if prime == 0:
            continue # 先に処理
        if prime > x_sqrt: 
            break
        for non_prime in range(2 * prime, x, prime):
            primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

q = int(input())
l_list = []
r_list = []
for _ in range(q):
    l, r = list(map(int,input().split()))
    l_list.append(l)
    r_list.append(r)
    
maxr = max(r_list)
p_list = primes(maxr+1)

sim_list = []
for p in p_list:
    if (p+1)/2 in p_list:
        sim_list.append(p)
        
cumulation = [0 for _ in range(maxr+1)]
for s in sim_list:
    cumulation[s] = 1

for i in range(1,len(cumulation)):
    cumulation[i] += cumulation[i-1]

for i in range(q):
    print(cumulation[r_list[i]]-cumulation[l_list[i]-1])

Submission status: Time Limit Exceeded

Solution code:
import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): #繰り返しの上限は平方根
        if q % divisor == 0: #平方根までに約数があれば合成数
            return False
    return True

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n): #nまでの素数をエラトステネスの篩で列挙
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

Q = int(input())
A = [0] * 100001 #A[0]からA[100000]までのリスト
A[3] = 1
S = sieve(100000)

for i in range(5,100001,4):
    if i in S and (i+1)/2 in S:
        A[i] = 1
for i in range(4,100001):
    A[i] += A[i-1]

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

Submission status: Time Limit Exceeded

Solution code:
import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): #繰り返しの上限は平方根
        if q % divisor == 0: #平方根までに約数があれば合成数
            return False
    return True

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n): #nまでの素数をエラトステネスの篩で列挙
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

Q = int(input())
qs = sieve(100000)

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

Submission status: Time Limit Exceeded

Solution code:
import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): #繰り返しの上限は平方根
        if q % divisor == 0: #平方根までに約数があれば合成数
            return False
    return True

Q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
l, r = [], []
for i in range(N):
  L,R=map(int,input().split())
  l+= [L]
  r+= [R]
  
prime = [0,0]+[1]*10**5#素数テーブル
for i in range(10**3):#エラトステネスのふるいにかける
  if prime[i]==0: continue
  for j in range(i+1,10**5+1):
    if j%i==0: prime[j]=0
  
ans = []
for i in range(10**5+1):
  if prime[i]:
    if prime[(i+1)//2]: ans+=[1]
    else: ans+=[0]
  else: ans+=[0]
ans2= [0]
for i in range(10**5):
  ans2+=[ans2[-1]+ans[i+1]]
for i in range(N): 
  print(ans2[r[i]]-ans2[l[i]-1])

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
isPrime = [True] * 100001
for p in range(2, 100001):
    if isPrime[p]:
       for i in range(p * p, 100001, p):
           isPrime[i] = False
           
isPrime[1],isPrime[2] = False,True
for i in range(Q):
    ans = 0
    l,r = map(int,input().split())
    for c in range(l,r+1,2):
        other = (c+1)//2
        if isPrime[c] == -1:
            for j in range(2,int(c**0.5)+1):
                if c % j == 0:
                    isPrime[c] = False
                    break
            else:
                isPrime[c] = True
        if isPrime[other] == -1:
            for j in range(2,int(other**0.5)+1):
                if other % j == 0:
                    isPrime[other] = False
                    break
            else:
                isPrime[other] = True
                
        if isPrime[c] and isPrime[other]:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
isPrime = [-1 for x in range(100001)]
isPrime[1],isPrime[2] = False,True
for i in range(Q):
    ans = 0
    l,r = map(int,input().split())
    for c in range(l,r+1,2):
        other = (c+1)//2
        if isPrime[c] == -1:
            for j in range(2,int(c**0.5)+1):
                if c % j == 0:
                    isPrime[c] = False
                    break
            else:
                isPrime[c] = True
        if isPrime[other] == -1:
            for j in range(2,int(other**0.5)+1):
                if other % j == 0:
                    isPrime[other] = False
                    break
            else:
                isPrime[other] = True
                
        if isPrime[c] and isPrime[other]:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    if n==0 or n==1:
        return False
    elif n==2:
        return True
    elif n % 2==0:
        return False
    else:
        for i in range(2,int(n**0.5)+1):
            if n % i ==0:
                return False
        else:
            return True


q=int(input())

for k in range(q):
    a,b=map(int,input().split())
    count=0
    for j in range(a,b+1,2):
        if prime(j) and prime((j+1)//2):
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
sosu  =[i+2 for i in range(99999)]
for i in range(len(sosu)):
    if sosu[i] != 0:
        i2 = (i+2)*2-2
        while i2 < len(sosu):
            sosu[i2] =0
            i2 += i+2
Q = int(input())
sosu.remove(0)
lis = []
for i in range(Q):
    lis.append(list(map(int,input().split())))
for i in lis:
    c,r = i
    count = 0
    while c <= r:
        if c in sosu:
            if int((c+1)/2) in sosu:
                count +=1
        c+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
sosu  =[i+2 for i in range(99999)]
for i in range(len(sosu)):
    if sosu[i] != 0:
        i2 = (i+2)*2-2
        while i2 < len(sosu):
            sosu[i2] =0
            i2 += i+2
Q = int(input())

lis = []
for i in range(Q):
    lis.append(list(map(int,input().split())))
for i in lis:
    c,r = i
    count = 0
    while c <= r:
        if c in sosu:
            if int((c+1)/2) in sosu:
                count +=1
        c+=1
    print(count)

Submission status: Time Limit Exceeded

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

p = set([2])


def isPrime(x):
    if x < 2:
        return False
    elif x in p:
        return True
    elif x % 2 == 0:
        return False

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

    p.add(x)
    return True


q = int(input())
pairs = []
for i in range(q):
    s, e = map(int, input().split())
    pairs.append((s, e))

for i in range(q):
    s, e = pairs[i]
    r = 0
    for j in range(s, e+1):
        if isPrime(j) and isPrime((j + 1) / 2):
            r += 1
    print(str(r))

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()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

#print min_n,max_n
#print a

C={}
cnt=0
for i in range(min_n, max_n+1):
	if is_prime(i) and is_prime( (i+1)/2 ):
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt
#print C

for i,j in a:
	if i==j:
		if C[i]>0:
			print 1
		else:
			print 0
	else:
		if i==min(C.keys()):
			print C[j]
		else:
			print C[j]-C[i-1]

Submission status: Time Limit Exceeded

Solution code:
import math

def hurui(n):
    li_tansaku = range(2, n + 1)
    li_sosu = []
    while True:
        i = li_tansaku[0]
        if i > math.sqrt(n):
            break
        
        li_sosu.append(i)
        li_tansaku = filter(lambda x: x % i != 0, li_tansaku)
    
    li_sosu.extend(li_tansaku)
    
    return li_sosu

def count_2017_liked_number(l, r):
    cnt = 0
    for i in range(l, r + 1):  
        if i not in li_sosu:
            continue
    
        if (i + 1) / 2 not in li_sosu:
            continue
    
        cnt += 1
        
    return cnt

if __name__ == "__main__":
    n = int(raw_input())
    lines = []
    max = 0
    for i in range(n):
        l, r = map(int, raw_input().split(" "))
        lines.append([l, r])
        if r > max:
            max = r
        
    li_sosu = hurui(max)
    for line in lines:
        print count_2017_liked_number(line[0], line[1])

Submission status: Time Limit Exceeded

Solution code:
import math

def hurui(n):
    li_tansaku = range(2, n + 1)
    li_sosu = []
    while True:
        i = li_tansaku[0]
        if i > math.sqrt(n):
            break
        
        li_sosu.append(i)
        li_tansaku = filter(lambda x: x % i != 0, li_tansaku)
    
    li_sosu.extend(li_tansaku)
    
    return li_sosu

def count_2017_liked_number(l, r):
    li_sosu = hurui(r)
    cnt = 0
    for i in range(l, r + 1):
        if i not in li_sosu:
            continue
        
        if (i + 1) / 2 not in li_sosu:
            continue
        
        cnt += 1
    
    return cnt

if __name__ == "__main__":
    n = int(raw_input())
    for i in range(n):
        l, r = map(int, raw_input().split(" "))
        print count_2017_liked_number(l, r)

Submission status: Time Limit Exceeded

Solution code:
def is_gusu(n):
    return n % 2 == 0

def is_sosu(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
    
def is_2017_liked_number(n):
    if is_gusu(n):
        return False
    
    if not is_sosu(n):
        return False
    
    if not is_sosu((n + 1) / 2):
        return False
        
    return True

def count_2017_liked_number(l, r):
    cnt = 0
    for i in range(l, r + 1):
        if is_2017_liked_number(i):
            cnt += 1 
    
    return cnt

if __name__ == "__main__":
    n = int(raw_input())
    for i in range(n):
        l, r = map(int, raw_input().split(" "))
        print count_2017_liked_number(l, r)