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
sys.setrecursionlimit(10 ** 7)


def eratosthenes(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return table


def main():
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]
    e = eratosthenes(10**5)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    q = int(input())
    p_s = primes()
    is_like_2017 = is_like_2017_function(p_s)
    for _ in range(q):
        l, r = map(int, input().split(' '))
        count = 0
        for i in range(l, r+1, 2):
            if is_like_2017(i):
                count += 1
        print(count)


def is_like_2017_function(primes):
    def _f(num):
        if num in primes and ((num+1)//2) in primes:
            return True
        else:
            False
    return _f


def primes():
    MAX = 10**5
    result = [True] * MAX
    result[0] = False
    loop_max = int(MAX**0.5) + 1
    for i in range(loop_max):
        if result[i]:
            for j in range((i+1)*2 - 1, MAX, (i+1)):
                if (j+1) % (i+1) == 0:
                    result[j] = False
    return [i+1 for i, b in enumerate(result) if b]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    def prime(n):
        if n<=1: return False
        A = [i for i in range(2, n+1)]
        P = []
        lim = n**.5
        while True:
            prime = A[0]
            if prime > lim: break
            P.append(prime)
            i = 0
            while i < len(A):
                if A[i] % prime == 0:
                    A.pop(i)
                    continue
                i += 1
        for a in A:
            P.append(a)
        return P

    C=5+10**5
    S=[0]*C
    T=[0]*C
    for p in prime(C):
        S[p]=1
    for i in range(C):
        if i%2==0: continue
        if S[i]==1 and S[(i+1)//2]==1:
            T[i]=1
    # cumsum
    for i in range(C-1):
        T[i+1]+=T[i]
    # input
    q=int(input())
    for _ in range(q):
        l,r=map(int,input().split())
        print(T[r]-T[l-1])
resolve()

Submission status: Time Limit Exceeded

Solution code:
import math
isPrime = [True for i in range(10**5+1)]
for i in range(3, 10**5+1):
    for j in range(2, math.floor(math.sqrt(i))+1):
        if i % j == 0:
            isPrime[i] = False

cntPrime = [0 for i in range(10**5+1)]
for i in range(2,10**5+1):
    if i % 2 == 1 and isPrime[i] and isPrime[(i+1)//2]:
        cntPrime[i] = cntPrime[i-1]+1
    else:
        cntPrime[i] = cntPrime[i-1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


def main():
    Q = int(input())
    is_prime, table = sieve(100000)
    N = []
    for p in table:
        if is_prime[(p+1)//2 - 1]:
            N.append(p)
    
    for _ in range(Q):
        l, r = map(int, input().split())
        cnt = 0
        for n in N:
            if l<=n and n<=r:
                cnt += 1
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


arr = get_sieve_of_eratosthenes(100000)

arr_2 = []

for i in range(1, len(arr)):
    if (arr[i] + 1) / 2 in arr:
        arr_2.append(arr[i])

Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    left_ind = bisect.bisect_left(arr_2, l)
    right_ind = bisect.bisect_right(arr_2, r)
    print(right_ind - left_ind)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    needed_prime = []
    data = [i + 1 for i in range(1, n)]
    i = 0
    for i in range(9592):
        p = data[0]
        prime.append(p)
        if int((p + 1) / 2) in prime and p != 2:
            needed_prime.append(p)
            #print(needed_prime)
        data = [e for e in data if (e % p != 0)]
    return needed_prime


arr = get_sieve_of_eratosthenes(100000)

Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    left_ind = bisect.bisect_left(arr, l)
    right_ind = bisect.bisect_right(arr, r)
    print(right_ind - left_ind)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if (e % p != 0)]


arr = get_sieve_of_eratosthenes(100000)

arr_2 = [e for e in arr if int((e + 1) / 2) in arr]


Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    left_ind = bisect.bisect_left(arr_2, l)
    right_ind = bisect.bisect_right(arr_2, r)
    print(right_ind - left_ind)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np


def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2, N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


pn = np.array(seachPrimeNum(100002))
pn2 = pn*2-1

n2017 = sorted(list(set(pn) & set(pn2)))

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(n2017, r)-bisect.bisect_left(n2017, l))

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())
Q = [list(map(int, input().strip().split(' '))) for _ in range(N)]

def make_primeset(N):
  prime_set = {2,3}
  for i in range(5,N+1):
    prime_flag = True
    for j in prime_set:
      if i % j == 0:
        prime_flag = False
        break
    if prime_flag:
      prime_set.add(i)
  return prime_set

max_i = max(q[1] for q in Q)
prime_set = make_primeset(max_i)

# 累積和
cusum = [0]*(max_i+1)

now = 0
for i in range(1,max_i+1,2):
  if i in prime_set and (i+1)//2 in prime_set:
    now += 1
  cusum[i] = now

for l,r in Q:
  if l == 1:
    print(cusum[r])
  else:
    print(cusum[r]-cusum[l-2])

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt, ceil

cache = set()
primes = {2}
def isprime(n):
    if n in primes:
        return True
    for i in range(3, ceil(sqrt(n))+1, 2):
        if n % i == 0:
            return False
    primes.add(n)
    return True

def solve(l, r):
    cnt = 0
    if l <= 3 <= r:
        cnt = 1
        l = 5
    if l % 4 == 3:
        l += 2
    for n in range(l, r+1, 4):
        if n in cache:
            cnt += 1
            continue
        m = (n - 1) // 2
        assert n % 4 == 1
        if isprime(m+1) and isprime(n):
            cache.add(n)
            cnt += 1
    return cnt

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

def check(l, r):
    print((l,r), solve(l,r))
"""
check(3, 7)
check(13, 13)
check(7, 11)
check(1, 11)
check(2017, 2017)
check(1, 53)
check(13, 91)
check(1, 10**5-1)
"""
main()

Submission status: Time Limit Exceeded

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


if __name__ == '__main__':
    data = set(get_sieve_of_eratosthenes(100000))
    pos = []
    for i in data:
        if (i + 1) % 2 == 0:
            if (i + 1) // 2 in data:
                pos.append(i)
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        ans = 0
        for i in pos:
            if i <= r and l <= i:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

def is_like_2017(num):
  if all([is_prime(num), is_prime(int((num+1)/2))]): return True
  else: return False
  
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

def get_prime_nums(N):
  nums = set([i for i in range(2,N+1)])
  for i in range(2, int(math.sqrt(N))+1):
    for j in range(2,int(N//i)+1):
      if i*j in nums: nums.remove(i*j)
  return nums

prime_nums = list(get_prime_nums(10**5))

Q = int(input())
for _ in range(Q):
  l,r = map(int, input().split())
  idx_l = bisect.bisect_left(prime_nums, l)
  idx_r = bisect.bisect_right(prime_nums, r)
 
  ans = 0
  for i in range(idx_l, idx_r):
    if is_like_2017(prime_nums[i]) is True:ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def is_like_2017(num):
  if all([is_prime(num), is_prime(int((num+1)/2))]): return True
  else: return False
  
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

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

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
lq = []
prime_numbers = [0,0,0]

for i in range(Q):
    tmp = list(map(int,input().split()))
    lq.append(tmp)

#素数判定 エラトステネスのふるい
sosu = [i for i in range(2,10**5 + 1)]
for a in sosu:
    sosu = [x for x in sosu if(x == a or x % a != 0)]

counter = 0

for j in range(3, 10 ** 5 + 1,2):
    if j in sosu:
        if j % 2 != 0 and (j+1)//2 in sosu:
            counter += 1
    prime_numbers.append(counter)

for k in lq:
    ans = prime_numbers[k[1]] - prime_numbers[k[0] - 1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
Ps = set()
M = [False]*100001
p = 2
while p <= 100000:
  if not(M[p]):
    Ps.add(p)
    for i in range(p, 100000, p):
      M[i] = True
  p += 1
#print(sorted(Ps))
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  re = 0
  for i in range(l, r+1, 2):
    if i in Ps and (i+1)//2 in Ps:
      re += 1
  print(re)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
lr=[[] for _ in range(N)]
for i in range(N):
  lr[i]=list(map(int,input().split()))

def f(n):
  if n==2:
    return 1
  elif n==1:
    return 0
  else:
    num=0
    for i in range(2,n):
      if n%i==0:
        num+=1
    if num==0:
      return 1
    else:
      return 0
def function(a,b):
  num=0
  for i in range(a,b+1):
    if f(i)==1 and f(int((i+1)/2))==1:
      num+=1
  return num

for i in range(N):
  print(function(lr[i][0],lr[i][1]))

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())

n=max(r)+1
sievebd=n//2-1
sieve=[True]*sievebd
limit=(int((n-1)**.5)-1)//2
for i in range(limit):
    if sieve[i]:
        for j in range(2*i**2+6*i+3,sievebd,2*i+3):
            sieve[j]=False
for i in range((sievebd-1)//2-1,-1,-1):
    if not sieve[i]:sieve[2*i+1]=False
if len(sieve)>2:
    for i in range(2,sievebd,2):
        sieve[i]=False
for i in range(q):
    print(sum(sieve[max(0,(l[i]-3)//2):max(0,(r[i]-3)//2+1)]))

Submission status: Time Limit Exceeded

Solution code:
n=10**5
sievebd=n//2-1
sieve=[True]*sievebd
limit=(int((n-1)**.5)-1)//2
for i in range(limit):
    if sieve[i]:
        for j in range(2*i**2+6*i+3,sievebd,2*i+3):
            sieve[j]=False
for i in range((sievebd-1)//2-1,-1,-1):
    if not sieve[i]:sieve[2*i+1]=False
for i in range(2,sievebd,2):sieve[i]=False
q=int(input())
for i in range(q):
    l,r=map(lambda x:max(int(x),3),input().split())
    print(sum(sieve[(l-3)//2:(r-3)//2+1]))

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(lambda x:max(int(x),3),input().split())

n=max(r)+1
sievebd=n//2-1
sieve=[True]*sievebd
limit=(int((n-1)**.5)-1)//2
for i in range(limit):
    if sieve[i]:
        for j in range(2*i**2+6*i+3,sievebd,2*i+3):
            sieve[j]=False
for i in range((sievebd-1)//2):
    if not sieve[i]:sieve[2*i+1]=False
if len(sieve)>2:
    for i in range(2,sievebd,2):
        sieve[i]=False
for i in range(q):
    print(sum(sieve[(l[i]-3)//2:(r[i]-3)//2+1]))

Submission status: Time Limit Exceeded

Solution code:
def primes(n,default=2):
    if n<3:return []
    sievebd=n//2-1
    sieve=[True]*sievebd
    limit=(int((n-1)**.5)-1)//2
    for i in range(limit):
        if sieve[i]:
            for j in range(2*i**2+6*i+3,sievebd,2*i+3):
                sieve[j]=False
    return [2]*(default==2)+[2*i+3 for i in range(default//2-1,sievebd) if sieve[i]]
def isprime(n):
    if n==1:
        return False
    elif n<4:
        return True
    elif n%2==0:
        return False
    elif n<9:
        return True
    elif n%3==0:
        return False
    else:
        r=int(n**.5)
        f=5
        while f<=r:
            if n%f==0:
                return False
            if n%(f+2)==0:
                return False
            f+=6
    return True
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
list=[]
for x in primes(max(r)+1,min(l)):
    if isprime((x+1)//2):
        list.append(x)
for i in range(q):
    c=0
    for x in list:
        if l[i]<=x<=r[i]:c+=1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())


# 約数
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
N = 5*10**4
acc = [0]*(N+1)
cnt = 0
for i in range(N+1):
    n1 = 2*i + 1
    n2 = i+1
    div1 = make_divisors(n1)
    div2 = make_divisors(n2)    
    if len(div1) == len(div2) == 2:
        cnt += 1
    acc[i] = cnt
# print(acc[:10])
for i in range(Q):
    l_,r_ = map(int, input().split())
    l = (l_-1)//2
    r = (r_-1)//2
    if l > 0:
        print(acc[r]-acc[l-1])
    else:
        print(acc[r])

Submission status: Time Limit Exceeded

Solution code:

import math

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


# まずは素数表を作る
ten5 = 10**5

x = get_sieve_of_eratosthenes(ten5)
P = [0] * (ten5+1)
for c in x:
    P[c] = 1

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

    print(count)

Submission status: Time Limit Exceeded

Solution code:
#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

q=int(input())
lr=[[int(x) for x in input().split()] for _ in range(q)]

max_n=max(sum(lr,[]))
primelist=primes(max_n)
for query in lr:
  res=0
  for item in range(query[0],query[1]+1,2):
    if (item in primelist) and ((item+1)/2 in primelist):
      res+=1
  print(res)

Submission status: Time Limit Exceeded

Solution code:
#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

q=int(input())
lr=[[int(x) for x in input().split()] for _ in range(q)]

max_n=max(sum(lr,[]))
primelist=primes(max_n)
for query in lr:
  print(sum([(item in primelist) and ((item+1)/2 in primelist) for item in range(query[0],query[1]+1,2)]))

Submission status: Time Limit Exceeded

Solution code:
def prime(i):
    if i == 1:
        return False
    if (i > 2) & (i % 2 == 0):
        return False
    for j in range(3, int(i**(0.5)) + 1, 2):
        if i % j == 0:
            return False
    return True



q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())
    for i in range(l, r+2, 2):
        if prime(i) & prime(int(i+1)//2):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
 
K = max(r)
prime = prime(K)
a = [0]*K
S = a + [0]
for i in range(K):
    if i+1 in prime and (i+2)/2 in prime:
        a[i] = 1

for i in range(K):
    S[i+1] = S[i] + a[i]

for i in range(Q):
    rr, ll = r[i], l[i]
    if rr == ll:
        if a[ll-1] == 1:
            print(1)
        else:
            print(0)
    else:
        print(S[rr-1] - S[ll-1])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

Q = int(input())
L = [0]*Q
R = [0]*Q

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

r = max(R)
A = list(range(2, r+1))
sqrt_r = r**(1/2)
idx = 0

while True:
    p = A[idx]
    if p > sqrt_r:
        break
    check_numbers = A[idx+1:]
    for check_number in check_numbers:
        if check_number % p == 0:
            A.remove(check_number)
    idx += 1

B = [0]*(r+1)
for i in A:
    if int((i+1)/2) in A:
        B[i] = 1

B = list(accumulate(B))

for i,j in zip(L,R):
    print(B[j]-B[i-1])

Submission status: Time Limit Exceeded

Solution code:
def erastotenes(n):
    prime=[2]
    limit=int(n**0.5)
    data=[i+1 for i in range(2, n, 2)]      #奇数のリストを作成
    while True:
        p=data[0]
        if p>=limit:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]


naturals=erastotenes(100000)

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    count=0
    for i in range(left, right+1):
        if i==1 or i%2==0:
            continue
        if i in naturals and int((i+1)/2) in naturals:
            count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def sieve(n):
    tmp=[i for i in range(n, 1, -1)]
    s=[]
    while len(tmp)>0:
        p=tmp.pop()
        s.append(p)
        for i in range(len(tmp), 0, -1):
            if tmp[-i]%p==0:
                del tmp[-i]
    return s

naturals=sieve(100000)

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    count=0
    for i in range(left, right+1):
        if i==1 or i%2==0:
            continue
        if i in naturals and int((i+1)/2) in naturals:
            count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#前計算
#素数のリスト作成
N = 10 ** 5 + 10
def primes(n):
    import math
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

prime_lst = primes(N)
# print (prime_lst, len(prime_lst))
count_lst = [0] * (N + 1)

def check(n):
    if n%2 == 0:
        return False
    if not n  in prime_lst:
        return False
    if not ((n + 1)//2) in prime_lst:
        return False
    return True


for i in range(3, N + 1):
    if check(i):
        count_lst[i] = count_lst[i - 1] + 1
    else:
        count_lst[i] = count_lst[i - 1]

# print (count_lst)

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

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
LR = [list(map(int,input().split())) for _ in [0]*Q]

N = max(r for l,r in LR)

p = set()
for i in range(3,N+1,2):
    for j in p:
        if i%j==0:break
    else:
        p.add(i)
p.add(2)

c = [0]*(N+1)
for i in p:
    if (i+1)//2 in p:c[i] = 1

#累積和
class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

Sc = cumulative_sum(c)

for l,r in LR:
    print(Sc.get(l,r+1))

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
like2017 = []

# def is_prime(x):
#     if x==2:
#         return True
#     elif x%2==0:
#         return False

#     for i in range(3, x, 2):
#         if x!=i and x%i==0:
#             return False
#     return True

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

for i in range(1, 10001, 2):
    if i>2 and is_prime(i) and is_prime(int((i+1)/2)):
        like2017.append(1)
    else:
        like2017.append(0)

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

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
like2017 = []

def is_prime(x):
    if x==2:
        return True
    elif x%2==0:
        return False

    for i in range(3, x, 2):
        if x!=i and x%i==0:
            return False
    return True

for i in range(1, 10001, 2):
    if i>2 and is_prime(i) and is_prime(int((i+1)/2)):
        like2017.append(1)
    else:
        like2017.append(0)

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

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
like2017 = []

def is_prime(x):
    if x==2:
        return True
    elif x%2==0:
        return False

    for i in range(3, x, 2):
        if x!=i and x%i==0:
            return False
    return True

for i in range(1, 10001):
    if i>2 and is_prime(i) and is_prime(int((i+1)/2)):
        like2017.append(1)
    else:
        like2017.append(0)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC84 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7


def get_prime(n):
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,n+1):
        for j in range(i*2,n+1,i):
            is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

prime = get_prime(10**5)
ansprime = [float('inf')]*(10**5)
for i in range(1,10**5+1,2):
    if i not in prime:
        continue
    if (i+1)//2 not in prime:
        continue
    ansprime[i] = i
ansprime.sort()
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    li = bisect.bisect_left(ansprime,l)
    ri = bisect.bisect_right(ansprime,r)
    print(ri-li)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import accumulate
q = int(stdin.readline().rstrip())
l_r = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
max_n = 0
for s in l_r:
    max_n = max(s[1], max_n)
# print(max_n)
# print(l_r)

a = [i for i in range(max_n+1)]

def isPrime(num):
    if num == 0 or num == 1:
        return False
    ans = True
    for i in range(2,int(num/2)+1):
        if num % i == 0:
            ans = False
            break
    return ans

b = [1 if isPrime(x) else 0 for x in a]
# print(b)
c = [1 if x == 1 and b[int((i+1)/2)] == 1 else 0 for i,x in enumerate(b)] 
# print(c)
s = list(accumulate(c))
# print(len(s))

for i in range(q):
    print(s[l_r[i][1]]-s[l_r[i][0]-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
import math
from itertools import chain

def input():
    return sys.stdin.readline().rstrip()

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

Q = int(input())
a = [list(map(int, input().split())) for _ in range(Q)]
s = []
min_num = min(list(chain.from_iterable(a)))
max_num = max(list(chain.from_iterable(a)))
ctr = 0

for j in range(min_num, max_num + 1, 2):
    if is_prime(j) and is_prime((j + 1) // 2):
        s.append(j)

for i in range(Q):
    for k in s:
        if k >= a[i][0] and k <= a[i][1]:
            ctr += 1
    print(ctr)
    ctr = 0

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
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

N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
ctr = 0

for i in range(N):
    for j in range(a[i][0], a[i][1] + 1, 2):
        if is_prime(j) and is_prime((j + 1) // 2):
            ctr += 1
    print(ctr)
    ctr = 0

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

def prime(n):
    # 素数列挙
    # nまでの素数をリストで返す(nを含む)
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5+1)):
        primes.difference_update(range(i*2, n+1, i))
    primes=list(primes)
    return primes

def count_num(n):
    cnt = 0
    prime_list = prime(n)
    prime_set = set(prime_list)
    for x in prime_list:
        if (x+1)//2 in prime_set:
            cnt += 1
    return cnt

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

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
LR=[[int(i) for i in input().split()] for _ in range(q)]
sosu=[False]*(10**5+1)
question=[0]*(10**5+1)
for i in range(2,10**5+1):
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            break
    else:
        sosu[i]=True
for i in range(3,10**5+1):
    if sosu[i] and sosu[(i+1)//2]:
        question[i]=1
for l,r in LR:
    print(sum(question[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
finished = [False] * 10**5
isPN = [False] * 10**5
def isPrimeNumber(num):
  if finished[num]:
    return isPN[num]
  
  if num == 1:
    return False
  pn = 2
  while pn * pn <= num:
    if num % pn == 0:
      finished[num] = True
      isPN[num] = False
      return isPN[num]
    pn += 1
  
  
  finished[num] = True
  isPN[num] = True
  return isPN[num]

n = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
def isPrimeNumber(num):
  if num == 1:
    return False
  pn = 2
  while pn * pn <= num:
    if num % pn == 0:
      return False
    pn += 1
  return True

n = int(input())

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