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:
q = int(input())

L = [True] * (10**5 + 1)

L[0], L[1] = False, False

for i in range(2, int((10**5) ** 0.5) + 1):
    if not L[i]:
        continue
    j = 2
    while i * j <= 10**5:
        L[i * j] = False
        j += 1

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

Submission status: Time Limit Exceeded

Solution code:
import math

def pri_num(n):
    for i in range(2,math.floor(n**0.5)+1):
        if n%i == 0:
            return 0
    return 1

def like_2017(n1):
    f2 = pri_num((n1+1)//2)
    if f2 == 0:
        return 0
    f1 = pri_num(n1)
    return f1*f2

Q = int(input())
memo = [-1]*(10**5+1)
for _ in range(Q):
    l,r= map(int,input().split())
    cnt = 0
    for i in range(l,r+1,2):
        if i%3 == 0 and i!=3:
            continue
        if i == 1:
            continue
        else:
            if memo[i] == -1:
                memo[i]= like_2017(i)
            cnt += memo[i]
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math

def pri_num(n):
    for i in range(2,math.floor(n**0.5)+1):
        if n%i == 0:
            return 0
    return 1

def like_2017(n1):
    f2 = pri_num((n1+1)//2)
    if f2 == 0:
        return 0
    f1 = pri_num(n1)
    return f1*f2

Q = int(input())
memo = [-1]*(10**5+1)
for _ in range(Q):
    l,r= map(int,input().split())
    cnt = 0
    for i in range(l,r+1,2):
        if i == 1:
            continue
        else:
            if memo[i] == -1:
                memo[i]= like_2017(i)
            cnt += memo[i]
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math

def pri_num(n):
    for i in range(2,math.floor(n**0.5)+1):
        if n%i == 0:
            return 0
    return 1

def like_2017(n1):
    f1 = pri_num(n1)
    f2 = pri_num((n1+1)//2)
    return f1*f2

Q = int(input())
memo = [-1]*(10**5+1)
for _ in range(Q):
    l,r= map(int,input().split())
    cnt = 0
    for i in range(l,r+1,2):
        if i == 1:
            continue
        else:
            if memo[i] == -1:
                memo[i]= like_2017(i)
            cnt += memo[i]
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

q = int(input())

def is_prime(n):
  if n==1:
    flg = False 
  else:
    flg = True
  for i in range(2, int(n**(1/2)+1)):
    if n%i==0:
      flg = False
    
  return flg

for _ in range(q):
  counter = 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):
      counter += 1
  
  print(counter)

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    prime_lst = []
    num_lst = []
    for i in range(2,n+1):
        if i not in num_lst:
            prime_lst.append(i)
            for j in range(i*i, n+1, i):
                #add all the dividers 
                num_lst.append(j)
        #print(prime_lst)
        #print(num_lst)
    return prime_lst
    
    
Q = int(input())
for i in range(Q):
    x = []
    l,r = map(int,input().split())
    for i in range(l,r+1,2):
        #print(i)
        lst = prime(i)
        if i in lst and (i+1)/2 in lst:
            x.append(i)

    print(len(x))

Submission status: Time Limit Exceeded

Solution code:
import math

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

MAX=10**5
limit=int(math.sqrt(MAX))
primes=[2]
table=[i+1 for i in range(2,MAX,2)]
while limit>table[0]:
  primes.append(table[0])
  table=[j for j in table if j%table[0] != 0]
table=primes+table

similars=[]
for i in range(len(table)):
  n=table[i]
  if (n+1)//2 in table:
    similars.append(n)

for i in lr:
  l=i[0]
  r=i[1]
  cand=[x for x in similars if l<=x<=r]
  print(len(cand))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    """
    エラトステネスの篩。√N以下の数に対して2から順にその数の倍数を消していく。
    計算量は「調和級数」になるのがミソ。具体的には
        N/2 + N/3 + N/5 + ... + N/(√N) = N * (1/2 + 1/3 + 1/5 + ... + 1/√N)
                                       = N * loglog(√N) (素数の逆数和の発散スピードがこれ)
                                       = N(loglogN - log2)
    """
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        return []
    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]


def main():
    primes = get_sieve_of_eratosthenes(100000)
    like = [0] * 10**5
    for i in range(3, 10**5):
        if i in primes and (i + 1) // 2 in primes:
            like[i] = 1
    like = list(accumulate(like))

    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        if l < 3: l = 3
        if r < 3:
            print(0)
            continue
        print(like[r] - like[l - 1])



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

a = [1]*(10**5+1)
a[0] = a[1] = 0

for i in range(2, ceil(sqrt(10**5)+1)):
    if a[i] == 0:
        continue
    else:
        if i == 2:
            a[i] = 0
        for j in range(i*2, len(a), i):
            a[j] = 0
            if j*2 - 1 < len(a):
                a[j*2-1] = 0

q = INT()
p = [LIST() for i in range(q)]

for i in range(q):
    print(sum(a[p[i][0]:p[i][1]+1]))

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
n=10**5

work=[1 if i%2==1 else 0 for i in range(n+1)]
primes=[2]
lst=[0]*(n+1)
work[1]==0

for i in range(3,n,2):
    if not work[i]: continue
    primes.append(i)
    index=1
    while i*index<=n:
        work[i*index]=0
        index+=1

for i in primes[1:]:
    if (i+1)//2 in primes:
        lst[i]=1

for _ in range(q):
    left,right=map(int,input().split())
    print(sum(lst[left:right+1]))

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
n=10**5

work=[1 if i%2==1 else 0 for i in range(n+1)]
primes=[2]
lst=[0]*(n+1)
work[1]==0

for i in range(3,n,2):
    if not work[i]: continue
    primes.append(i)
    index=1
    while i*index<=n:
        work[i*index]=0
        index+=1

for i in primes[1:]:
    if (i+1)//2 in primes:
        lst[i]=1

for _ in range(q):
    left,right=map(int,input().split())
    print(sum(lst[left:right+1]))

Submission status: Time Limit Exceeded

Solution code:
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
	
N=generate_is_prime_sieve(10**5+1)
for i in range(int(input())):
	counter=0
	a,b=[int(x) for x in input().split()]
	for i in range(a,b+1):
		if N[i] and N[(i+1)//2]:
			counter+=1
	print(counter)

Submission status: Time Limit Exceeded

Solution code:
import math

q = int(input())

def is_prime(a):
    if a == 1:
        return False
    for i in range(2,int(math.sqrt(a)+1)):
        if a%i == 0:
            return False
    else:
        return True

s = [0 for i in range(0,100001)]
for i in range(3,100001,2):
    if is_prime(i) and is_prime((i+1)//2):
        s[i] = 1

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

Submission status: Time Limit Exceeded

Solution code:
import math

q = int(input())

s = [i for i in range(2,100001) if i%2!=0 and i%3!=0 and i%5!=0]
sosu = [2,3,5]
while math.sqrt(100000) <= s[0]:
    sosu.append(s[0])
    for s_num in range(s[0],s[-1]+1,s[0]):
        if s_num in s:
            s.remove(s_num)
sosu = sosu + s
            
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for j in range(l,r+1,2):
        if j in sosu and (j+1)//2 in sosu:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

q = int(input())

def sosu(a):
    for i in range(2,math.ceil(math.sqrt(a))+1):
        if a%i == 0:
            dic[a] = 0
            break
    else:
        dic[a] = 1

dic = {1:0,2:1,3:1}
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for j in range(l,r+1,2):
        if j not in dic:
            sosu(j)
        if (j+1)//2 not in dic:
            sosu((j+1)//2)
        if dic[j] == 1 and dic[(j+1)//2] == 1:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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


def prime_factorization(num):
    sqrt_num = math.sqrt(num)
    prime_numbers = []
    for i in range(2, int(sqrt_num) + 1):
        # print(num)
        while num % i == 0:
            # print(num)
            num = num / i
            prime_numbers.append(i)
    if num != 1:
        prime_numbers.append(int(num))
    return prime_numbers


for i in range(Q):
    l, r = map(int, input().split())
    count = 0
    for k in range(l, r + 1):
        if k % 2 == 1:
            # print(k)
            if len(prime_factorization(k)) == 1 and len(prime_factorization((k + 1) // 2)) == 1:
                count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

def factorization(n):
  divided = n
  prime_factor = []

  for i in range(2, int(math.sqrt(n)//1)+1):
    while divided%i == 0:
      prime_factor.append(i)
      divided //= i
  if divided != 1:
    prime_factor.append(divided)
  
  return prime_factor

Q = int(input())
ans = []
for _ in range(Q):
  counter = 0
  l, r = map(int, input().split())
  for odd in range(l, r+1, 2):
    if len(factorization(odd)) == 1 and len(factorization((odd+1)/2)) == 1:
      counter += 1
  ans.append(counter)

for item in ans:
  print(item)

Submission status: Time Limit Exceeded

Solution code:
import math
def factorize(p):
    l = []
    while p % 2 == 0:
        p //= 2
        l.append(2)
        
    r = 3
    while r < int(math.sqrt(p)+1):
        if p % r == 0:
            p //= r
            l.append(r)
        else:
            r += 2
            
    if p != 1:
        l.append(p)
        
    return l

Q = int(input())
ans_list = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans = 0
    if r==1:
        ans_list.append(ans)
    else:
        if l==1:
            l=3
        for i in range(l, r+1, 2):
            num_list = factorize(i)
            if len(num_list) == 1:
                if len(factorize((num_list[0]+1)/2)) == 1:
                    ans += 1
        ans_list.append(ans)
for i in ans_list:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import math
def eraP(n):
    if n<=1: return [False]*(n+1)
    elif n<=2: return [False, False, True]
    L = [False if i%2==0 or i%3==0 else True for i in range(n)]
    L[0] = False; L[1] = False;
    L[2] = True; L[3] = True; L[5]=True
    limit = math.sqrt(n)
    for i in range(3,n,2):
        if i >= limit: return L
        for s in range(i**2,n,i):
            L[s] = False
    return L

q = int(input())
rmax = 0
L = [0]*q
R = [0]*q
for i in range(q):
    l, r = map(int, input().split())
    L[i], R[i] = l, r
    rmax = max(r,rmax)
P = eraP(rmax+1)

for i in range(q):
    tmp = 0
    for j in range(L[i],R[i]+1):
        if P[j] and P[(j+1)//2]:
            tmp += 1
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
lr=[list(map(int,input().split())) for i in  range(q)]
MAX=10**5+1
l=[0]*MAX

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

	for i in  range(2,int(n**0.5)+1):
		if n % i == 0:
			return  False
	return  True
  
for i in range(1, MAX, 2):
  if is_prime(i) and is_prime((i+1)/2):
    l[i]=1


for i in range(q):
  #print(l[:lr[i][1]+1],l[:lr[i][0]])
  print(sum(l[:lr[i][1]+1]) - sum(l[:lr[i][0]]))

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    else:
        for p in range(2, n):
            if n % p == 0:
                return False
        else:
            return True


# input
Q = int(input())
LR = [tuple(map(int, input().split())) for q in range(Q)]

# check
SimilarNumbersTo2017 = [
    len([n for n in range(l, r + 1, 2) if is_prime(n) and is_prime((n + 1) // 2)])
    for l, r in LR
]

for ans in SimilarNumbersTo2017:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 累積和

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

# ナイーブな実装
def calc(l, r):
    ans = 0
    # 処理系
    for i in range(l, r+1):
        if is_prime(i) and is_prime((i+1)//2):
            ans += 1
    return ans

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(calc(l, r))

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
l_lst = []
r_lst = []
for i in range(q):
  l, r = map(int, input().split())
  l_lst.append(l)
  r_lst.append(r)
max_ = max(r_lst)

primes = [2]
for L in range(3, max_+1, 2):
    for L2 in primes:
        if L % L2 == 0:
            break
    else:
        primes.append(L)
        
for l, r in zip(l_lst, r_lst):
  cnt = 0
  for j in range(l, r+1):
    if j in primes and (j+1)//2 in primes:
      cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
primes = [2]
for L in range(3, 100000, 2):
    for L2 in primes:
        if L % L2 == 0:
            break
    else:
        primes.append(L)

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

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
lr = [list(map(int,input().split())) for _ in range(q)]
def primesFactraizar(n):
    is_prime = [True] * (n + 1) #まずは[1]*nを用意
    is_prime[0] = False 
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1): #素数の判定√nまでで十分
        if not is_prime[i]: #非素数は無視
            continue            #continue分はループ中の後続の命令をスキップする
        for j in range(i * 2, n + 1, i): #i*2~nまでのiの倍数を順番に消す
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
primes = primesFactraizar(10**5+1)

cumSum = [0]*(10**5+1)
tmp = 0
for i in range(10**5+1):
    if i in primes and (i+1)//2 in primes:
        tmp += 1 
    cumSum[i] = tmp


for l,r in lr:
    print(cumSum[r]-cumSum[l-1])

Submission status: Time Limit Exceeded

Solution code:
def primesFactraizar(n):
    is_prime = [True] * (n + 1) #まずは[1]*nを用意
    is_prime[0] = False 
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1): #素数の判定√nまでで十分
        if not is_prime[i]: #非素数は無視
            continue            #continue分はループ中の後続の命令をスキップする
        for j in range(i * 2, n + 1, i): #i*2~nまでのiの倍数を順番に消す
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
primes = primesFactraizar(10**5+1)

cumSum = [0]*(10**5+1)
tmp = 0
for i in range(10**5+1):
    if i in primes and (i+1)//2 in primes:
        tmp += 1 
    cumSum[i] = tmp

q=int(input())
lr = [list(map(int,input().split())) for _ in range(q)]
for l,r in lr:
    print(cumSum[r]-cumSum[l-1])

Submission status: Time Limit Exceeded

Solution code:
import math
q = int(input())
s = [-1]*100001


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]


x = get_sieve_of_eratosthenes(10**5)
for j in x:
    s[j] = 0
for i in range(q):
    ans = 0
    a, b = map(int, input().split())
    for k in range(a, b+1, 2):
        ans += (s[k] == 0 and s[(k+1)//2] == 0)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
q = int(input())
dp = [0]*(100001)
dp[0] = 1
dp[1] = 1
dp[2] = 1
for j in range(2,int(math.sqrt(100000)+1)):
  for k in range(j*2,100001,j):
    dp[k] = 1
    if k*2-1 <= 100000:
      dp[k*2-1] = 1
for i in range(q):
  l,r = map(int,input().split())
  ans = dp[l:r+1].count(0)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
q = int(input())
for i in range(q):
  l,r = map(int,input().split())
  dp = [0]*(r+1)
  dp[0] = 1
  dp[1] = 1
  dp[2] = 1
  for j in range(2,int(math.sqrt(r)+1)):
    for k in range(j*2,r+1,j):
      dp[k] = 1
      if k*2-1 <= r+1:
        dp[k*2-1] = 1
  ans = dp[l:r+1].count(0)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
ans=0
a=[]
sosuu = [2]
A = 2018
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        
for i in (sosuu):
    if (i+1)/2 in sosuu:
        a.append(i)
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        if j in (a):
            ans+=1
    print(ans)
    ans=0

Submission status: Time Limit Exceeded

Solution code:
import math

def is_prime(N):
  if N == 1:
    return
  if N % 2 ==0:
    return
  for i in range(2,N):
    if N % i == 0:
      return
  return N

def si_prime(N):
  if N%2==0:
    return
  N=int((N+1)/2)
  for i in range(2,N):
    if N%i==0:
      return
  return N
  
q=int(input())
a=[list(map(int,input().split())) for _ in range(q)]

for i in a:
  count=0
  for j in range(i[0],i[1]+1):
    x=is_prime(j)
    y=si_prime(j)
    if x!=None and y!=None:
      count+=1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
    if n == 1: 
        return False
    x = 2
    while x*x<=n:
        if n%x==0:
            return False
        x+=1
    return True

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 table

sosuu = sieve(100000)
like_2017 = [i for i in sosuu if is_prime((i+1)//2)]
q = int(input())
for i in range(q):
  l,r = map(int,input().split())
  print(len([i for i in like_2017 if i>=l and i<=r]))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


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

    dp = [1] * (MAX + 1)
    dp[0] = dp[1] = 0
    for i in range(2, MAX + 1):
        if dp[i]:
            x = 2
            while i * x < MAX + 1:
                dp[i * x] = 0
                x += 1
    for i in reversed(range(2, MAX + 1)):
        if not dp[(i + 1) // 2]:
            dp[i] = 0
    for l, r in lr:
        print(sum(dp[l:r + 1]))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

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


l=[]
r=[]
q=int(input())
for i in range(q):
    ll,rr=map(int,input().split())
    l.append(ll)
    r.append(rr)

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

Submission status: Time Limit Exceeded

Solution code:
#ABC084D
def main():
    import sys
    Q = int(sys.stdin.readline())
    LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    #print(LR)
    
    check = [1 for _ in range(10**5+1)]
    check[0], check[1] = 0, 0
    for i in range(2, 10**5+1):
        if check[i] ==0:
            continue
        elif check[i] ==1:
            for j in range(2*i, 10**5+1, i):
                check[j] =0
    check2 = check.copy()
    for i in range(2, 10**5+1):
        if check[i]==1:
            #print((i+1)/2, check[(i+1)//2])
            if (i+1)%2==0 and check[(i+1)//2] ==1:
                continue
            else:
                check2[i] = 0
    
    #print(check)
    for lr in LR:
        #print(lr[0], lr[1])
        print(check2[lr[0]:lr[1]+1].count(1))
                


if __name__ =='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=10**5
prime=[0]*(N+1)
for n in range(2,N+1):
  if all([n%i for i in range(2,int(n**.5)+1)]):
      prime[n]=1

check=[0]*(N+1)
for n in range(N+1):
    if n%2==1 and prime[n] and prime[(n+1)//2]:
        check[n]=1

accumulate=[0]*(N+1)
for n in range(1,N+1):
    accumulate[n]=accumulate[n-1]+check[n]

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

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
for q in range(Q):
    l,r=map(int,input().split())
    count=0
    for N in range(l,r+1,2):
        if all([N%i for i in range(2,int(N**.5)+1)]) and all([((N+1)/2)%i for i in range(2,int(((N+1)/2)**.5)+1)]) and N!=1:
            count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
for i in range(q):   
    l,r=map(int,input().split())
    ans=0
    for j in range(l,r+1,2):
        k=(j+1)//2
        if j==1:
            continue
        if k==2:
            ans+=1
            continue
        flg=True
        for h in range(2,int(j**(1/2))+1):
            if j%h==0:
                flg=False
        for s in range(2,int(k**(1/2))+1):
            if k%s==0:
                flg=False
        if flg:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def sPN(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

n = int(input())

p = sPN(100000)

pp = []

for i in p:
    if (i+1)//2 in p:
        pp.append(i)

import bisect

for i in range(n):
    a,b = map(int, input().split())
    temp = bisect.bisect(pp,b)-bisect.bisect(pp,a)
    if a in pp:
        temp +=1    
    print(temp)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def sPN(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

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

p = sPN(100000)

pp = []

for i in p:
    if (i+1)//2 in p:
        pp.append(i)

import bisect

for i in range(n):
    temp = bisect.bisect(pp,ab[i][1])-bisect.bisect(pp,ab[i][0])
    if ab[i][0] in pp:
        temp +=1    
    print(temp)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def sPN(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

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

p = sPN(100000)

import bisect

for i in range(n):
    temp = 0
    for j in range(ab[i][0],ab[i][1]+2,2):
        if j in p and (j+1)//2 in p:
            temp +=1
    print(temp)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

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

def primes(n):
    # 1であれば素数であるリスト
    primes = [1] * (n+1)
    primes[0] = 0
    primes[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not primes[i]:
            continue
        for j in range(i * 2, n + 1, i):
            primes[j] = 0
    return primes

MAX = 100000
prime_cumsum = primes(MAX)
# 2017に似た数値かどうかを更新
for i in range(MAX, -1, -1):
    if prime_cumsum[i] == 0:
        continue
    if prime_cumsum[(i+1)//2] == 0:
        prime_cumsum[i] = 0

for i in range(q):
    print(sum(prime_cumsum[lr[i][0]:lr[i][1]+1]))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

prime_numbers = set()
input = lambda: sys.stdin.readline().strip()


def is_primenumber(x):
    if x in prime_numbers:
        return True
    if x == 1:
        return False
    elif x == 2:
        prime_numbers.add(2)
        return True
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        prime_numbers.add(x)
        return True


def query(l, r):
    count = 0
    for x in range(l, r + 1, 2):
        if is_primenumber(x) and is_primenumber((x + 1) // 2):
            count += 1
    print(count)


if __name__ == "__main__":
    for i in range(1, 10 ** 5 + 1):
        is_primenumber(i)
    Q = int(input())

    for _ in range(Q):
        l, r = [int(x) for x in input().split(" ")]
        query(l, r)

Submission status: Time Limit Exceeded

Solution code:
import math
import time

prime_numbers = set()


def is_primenumber(x):
    if x in prime_numbers:
        return True
    if x == 1:
        return False
    elif x == 2:
        prime_numbers.add(2)
        return True
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        prime_numbers.add(x)
        return True


def query(l, r):
    count = 0
    for x in range(l, r + 1, 2):
        if is_primenumber(x) and is_primenumber((x + 1) // 2):
            count += 1
    print(count)


# e = time.time()
# print(e - s)
if __name__ == "__main__":
    for i in range(1, 10 ** 5 + 1):
        is_primenumber(i)
    Q = int(input())

    for _ in range(Q):
        l, r = [int(x) for x in input().split(" ")]
        query(l, r)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

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

# 素数判定
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False

    return True

for i in range(q):
    cnt = 0
    for j in range(lr[i][0], lr[i][1]+1):
        if not is_prime(j):
            continue
        if is_prime((j+1)//2):
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

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

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

primes=[]
for i in range(10**5+1):
    if is_prime(i) and is_prime((i+1)//2):
        primes.append(1)
    else:
        primes.append(0)

for l,r in lr:
    sum=0
    for i in range(l,r+1):
        sum+=primes[i]
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
import sys
input = sys.stdin.readline
q = int(input())
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            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

prime = set(eratosthenes(10**5))
like = []
for p in prime:
    if (p+1)//2 in prime:
        like.append(p)
like.sort()

for i in range(q):
    l, r = map(int, input().split())
    st = bisect.bisect_left(like, l)
    en = bisect.bisect_left(like, r)

    print(en-st)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
q = int(input())
lr = [list(map(int, input().split())) for i in range(q)]

def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            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

prime = set(eratosthenes(10**5))
like = []
for p in prime:
    if (p+1)//2 in prime:
        like.append(p)
like.sort()

for l, r in lr:
    st = bisect.bisect_left(like, l)
    en = bisect.bisect_left(like, r)

    print(en-st)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc084/tasks/abc084_d

Nmax = 10**6 + 1

def prime_test(n):
    if n == 1:
        return False
    i = 2
    while i*i<=n:
        if n%i:
            i += 1
        else:
            return False
    return True

cum = [0]*Nmax

for n in range(1,Nmax,2):
    if prime_test(n) and prime_test((n + 1)/2):
        cum[n] = cum[n-2] + 1
    else:
        cum[n] = cum[n - 2]

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