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
import numpy as np

Q = int(input())
LR = []

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    # print(int(math.sqrt(n)))
    for i in range(2,int(math.sqrt(n))+1):
        for j in range(i*2, n+1 ,i):
            is_prime[j] = False

    return is_prime

def like2017(is_prime,n):
    solve = [False] * (n+1)
    for i in range(3,n+1,2):
        if i < n and i >2:
            solve[i] = is_prime[i] and is_prime[int((i+1)/2)]

    return solve

for _ in range(Q):
    t = [int(i) for i in input().split(' ')]
    LR.append(t)

L = 10**5 
is_prime = primes(L)
solve = like2017(is_prime,L)
# solve = np.ndarray(solve)
for l, r in LR:
    print(sum(solve[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())
LR = []

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    # print(int(math.sqrt(n)))
    for i in range(2,int(math.sqrt(n))+1):
        for j in range(i*2, n+1 ,i):
            is_prime[j] = False

    return is_prime

def like2017(is_prime,n):
    solve = [False] * (n+1)
    for i in range(3,n+1,2):
        if i < n and i >2:
            solve[i] = is_prime[i] and is_prime[int((i+1)/2)]

    return solve

for _ in range(Q):
    t = [int(i) for i in input().split(' ')]
    LR.append(t)

L = 10**5 
is_prime = primes(L)
solve = like2017(is_prime,L)
for l, r in LR:
    # print(solve[l:r+1])
    print(solve[l:r+1].count(True))

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
k = 10**5
a=[1]*k
good_prime=[]


table = [int(i) for i in range(k)]
def hurui():
    a[0]=a[1]=0
    for i in range(2, k):
        if(a[i]):
            j=i*2
            while(j<k):
                a[j]=0
                j+=i
hurui()

def is_good():
    for i, j in enumerate(a):
        if i==0 or i==1:continue
        if j==1:
            if(a[(i+1)//2])==1:
                good_prime.append(i)

is_good()
for _ in range(n):
    ans=0
    l,r=map(int, input().split())
    for i in good_prime:
        if i>r:break
        if i>=l and i<=r:
            ans+=1
    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

Q = int(input())
lr_list = [list(map(int,input().split())) for _ in range(Q)]
flags = [False] * (10 ** 5)


for i in range(1, 10 ** 5 + 1, 2):
    if not flags[i]:
        flag1 = is_prime(i)
        flag2 = is_prime((i + 1) // 2)
        if flag1 and flag2:
            flags[i] = True

for l, r in lr_list:
    print(sum(flags[l: r + 1]))

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

Q = int(input())
lr_list = [list(map(int,input().split())) for _ in range(Q)]
flags = [0] * (10 ** 5)


for l, r in lr_list:
    ans = 0
    for i in range(l, r + 1, 2):
        if flags[i] == -1:
            continue
        elif flags[i] == 0:
            flag1 = is_prime(i)
            flag2 = is_prime((i + 1) // 2)
            if flag1 and flag2:
                flags[i] = 1
            else:
                flags[i] = -1
        if flags[i] == 1:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
memo = [0]*100000

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


cnt = 0
tmp = 0
for _ in range(Q):
    l, r = map(int, input().split())

    for i in range(l, r+1,2):
        tmp = (i+1)//2
        if memo[i] == 2:
            if memo[tmp] == 2:
                cnt += 1
            elif memo[tmp] == 1:
                continue
            elif memo[tmp] == 0:
                if is_prime(tmp):
                    cnt += 1

        elif memo[i] == 1:
            continue

        elif memo[i] == 0:
            if is_prime(i):
                if is_prime(tmp):
                        cnt += 1

    print(cnt)
    cnt = 0

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

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


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

    for i in range(l, r + 1, 2):
        if is_prime(i) and is_prime((i + 1) // 2):
            cnt += 1

    print(cnt)
    cnt = 0

Submission status: Time Limit Exceeded

Solution code:
import math

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


def prime(n):
	if n > 1:
		for i in range(2,math.floor(math.sqrt(n))+1):
			if (n % i) == 0:
				return(False)
				break
		else:
			return(True)
	else:
		return(False)

count = 0
for i in range (0, Q):
	for j in range (P[i][0], P[i][1]+1):
		if j%2==0:
			continue
		else:
			if prime(j) == 1 and prime((j+1)/2) == 1:
				count+=1
			else:
				continue
	print(count)
	count=0

Submission status: Time Limit Exceeded

Solution code:
def prime_number(k):
    if 1 < k < 4:
        return True
    if k % 2 == 0 or k == 1:
        return False
    for n in range(2, int(k ** 0.5)+1):
        if k % n == 0:
            return False
    return True


def main():
    Q = int(input())
    prime_number_list = list()
    list_2017 = list()
    for _ in range(Q):
        L, R = map(int, input().split(' '))
        if L % 2 == 0:
            L += 1
        cnt = 0
        for i in range(L, R + 1, 2):
            if i in list_2017:
                cnt += 1
                continue
            if i not in prime_number_list:
                if prime_number(i):
                    prime_number_list.append(i)
                else:
                    continue
            if (i + 1)//2 not in prime_number_list:
                if prime_number((i + 1) // 2):
                    prime_number_list.append((i + 1) // 2)
                else:
                    continue
            cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def isprime(x):
  if x==1:
    return False
  if x==2:
    return True
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      return False
  return True

def like2017(x):
  return (isprime(x) and isprime((x+1)//2))

a=[like2017(i) for i in range(10**5+1)]

a_cum=np.cumsum(a)

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

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5) + 1):
        # 既にfalseになってたらスキップ
        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_ls = primes(10**5)

def isOK(index, key, l):
    if l[index] >= key:
        return True
    else:
        return False

def meguru_search(l, key):
    left = -1
    right = len(l)

    while (right - left) > 1:
        mid = left + (right - left) // 2
        # 直感的に記憶　
            # 「含まれている」んだったら「含むを許容（等号付き）する右側」はmidまで動かして問題ない
                # 新しいrightの位置がkeyの位置だとしても、「含む」は許容されてる
            # 「含まれていない」んだったら「含まない(<)左の壁」をそこまで動かしてもkeyを通り過ぎることはない
        if isOK(mid, key, l):
            right = mid
        else:
            left = mid
    
    # whileを抜ける時、rightとleftは一個差で、かつkeyがrightの位置にある
    return right

def binary_search(l, item):
    left = 0
    right = len(l) - 1
    while left <= right:
        mid  = (left + right) // 2
        if l[mid] == item:
            return True
        elif l[mid] < item:
            left = mid + 1
        else:
            right = mid - 1
    return False

ans_ls = [0] * q
for i in range(q):
    l,r = map(int,input().split())
    start = meguru_search(prime_ls, l)
    end = meguru_search(prime_ls, r)
    target = prime_ls[start:end+1]
    ans = 0
    # ↓ここで枝切りしてから、「+1」の条件をチェックしたい
    for prime in target:
        if binary_search(prime_ls, (prime + 1)// 2):
                ans += 1
    ans_ls[i] = ans
for ans in ans_ls:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5) + 1):
        # 既にfalseになってたらスキップ
        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_ls = primes(10**5)

def binary_search(l, item):
    left = 0
    right = len(l) - 1
    while left <= right:
        mid  = (left + right) // 2
        if l[mid] == item:
            return True
        elif l[mid] < item:
            left = mid + 1
        else:
            right = mid - 1
    return False

ans_ls = [0] * q
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for j in range(l,r+1):
        if binary_search(prime_ls, j):
            # 2は例外として処理したい
            if binary_search(prime_ls, (j + 1)// 2):
                ans += 1
    ans_ls[i] = ans
for ans in ans_ls:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

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

List = [3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541, 613, 661, 673, 733, 757, 877, 997, 1093, 1153, 1201, 1213, 1237, 1321, 1381, 1453, 1621, 1657, 1753, 1873, 1933, 1993, 2017, 2137, 2341, 2473, 2557, 2593, 2797, 2857, 2917, 3061, 3217, 3253, 3313, 3517, 3733, 4021, 4057, 4177, 4261, 4273, 4357, 4441, 4561, 4621, 4933, 5077, 5101, 5113, 5233, 5413, 5437, 5581, 5701, 6037, 6073, 6121, 6133, 6217, 6337, 6361, 6373, 6637, 6661, 6781, 6997, 7057, 7213, 7393, 7417, 7477, 7537, 7753, 7933, 8053, 8101, 8221, 8317, 8353, 8461, 8521, 8677, 8713, 8893, 9013, 9133, 9181, 9241, 9277, 9601, 9661, 9721, 9817, 9901, 9973]

for i in range (0, Q):
	count = 0
	for j in range (P[i][0],P[i][1]+1):
		if j%2 == 0:
			continue
		elif List.count(j) >0:
			count+=1
		else:
			continue
	print(count)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

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

List = [3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541, 613, 661, 673, 733, 757, 877, 997, 1093, 1153, 1201, 1213, 1237, 1321, 1381, 1453, 1621, 1657, 1753, 1873, 1933, 1993, 2017, 2137, 2341, 2473, 2557, 2593, 2797, 2857, 2917, 3061, 3217, 3253, 3313, 3517, 3733, 4021, 4057, 4177, 4261, 4273, 4357, 4441, 4561, 4621, 4933, 5077, 5101, 5113, 5233, 5413, 5437, 5581, 5701, 6037, 6073, 6121, 6133, 6217, 6337, 6361, 6373, 6637, 6661, 6781, 6997, 7057, 7213, 7393, 7417, 7477, 7537, 7753, 7933, 8053, 8101, 8221, 8317, 8353, 8461, 8521, 8677, 8713, 8893, 9013, 9133, 9181, 9241, 9277, 9601, 9661, 9721, 9817, 9901, 9973]

for i in range (0, Q):
  count = 0
  for j in range (P[i][0],P[i][1]+1):
    if List.count(j) >0:
      count+=1
    else:
      continue
  print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import math

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

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

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

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


def resolve():
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]
    max_r = max([r for l, r in lr])

    # 素数のlist
    prime_list = primes(max_r + 1)

    """
    # 10^5 * 10 ^ 5なので✗
    for l, r in lr:
        tmp = 0
        for i in range(l, r + 1):
            if i in prime_list and (i + 1)/2 in prime_list:
                tmp += 1
        print(tmp)
    """

    for l, r in lr:
        tmp = 0
        for i in [prime for prime in prime_list if prime >= (l + 1)/2 and prime <= (r + 1)/2]:
            if 2 * i - 1 in prime_list:
                tmp += 1
        print(tmp)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """1
3 7"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
13 13
7 11
7 11
2017 2017"""
        output = """1
0
0
1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
1 53
13 91
37 55
19 51
73 91
13 49"""
        output = """4
4
1
1
1
2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import math

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

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

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

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


def resolve():
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]
    max_r = max([r for l, r in lr])

    # 素数のlist
    prime_list = primes(max_r + 1)

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


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """1
3 7"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
13 13
7 11
7 11
2017 2017"""
        output = """1
0
0
1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
1 53
13 91
37 55
19 51
73 91
13 49"""
        output = """4
4
1
1
1
2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

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


# 素数判定
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

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(pow(10,5))
ans=[]
for i in range(len(v)):
    x=(v[i]+1)//2
    index = bisect.bisect_left(v, x)
    if v[index]==x:
        ans.append(v[i])

for i,j in s:
    r = bisect.bisect_left(ans, j+1)
    l = bisect.bisect_left(ans, i-1)
    print(r-l)

Submission status: Time Limit Exceeded

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


# 素数判定
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

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(10**5)
w=[0]*(10**5+1)
for i in range(len(v)):
    w[v[i]]+=1

for i in range(10**5,0,-1):
    if w[i]==1:
        if w[(i+1)//2]==1:
            continue
        else:
            w[i]=0
w=list(itertools.accumulate(w))

for i,j in s:
    print(w[j+1] -w[i-1])

Submission status: Time Limit Exceeded

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


# 素数判定
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

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(10**5)
w=[0]*(10**5+1)
for i in range(len(v)):
    w[v[i]]+=1

for i in range(10**5,0,-1):
    if w[i]==1:
        if w[(i+1)//2]==1:
            continue
        else:
            w[i]=0
w=list(itertools.accumulate(w))

for i,j in s:
    print(w[j+1] -w[i-1])

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools


# 素数判定
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

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(10**5)
w=[0]*(10**5+1)
for i in range(len(v)):
    w[v[i]]+=1

for i in range(10**5,0,-1):
    if w[i]==1:
        if w[(i+1)//2]==1:
            continue
        else:
            w[i]=0
w=list(itertools.accumulate(w))


for i,j in s:
    print(w[j+1] -w[i-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc084/tasks/abc084_d
# 18:49-19:10 中断
# 0:21-0:45


def prime_set(limit=10**5):
    ret = [2]
    for x in range(3, limit+1, 2):
        is_prime = True
        sqrtx = int(pow(x, 0.5))

        for p in ret:
            if p > sqrtx:
                break

            if x % p == 0:
                is_prime = False
                break

        if is_prime:
            ret.append(x)

    return ret


def bin_search(xs, start, end, x):
    idx = start + (end-start) // 2
    if x < xs[idx]:
        return bin_search(xs, start, idx, x)
    elif x > xs[idx]:
        return bin_search(xs, idx+1, end, x)
    else:
        return idx


def main():
    primes = prime_set()
    primes_set = set(primes)
    len_primes = len(primes)

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

    # output = 0

    for i in range(Q):
        output = 0

        left, right = l[i], r[i]
        while True:
            if left in primes_set:
                break

            left += 2
        while True:
            if right in primes_set:
                break

            right -= 2

        left_idx = bin_search(primes, 0, len_primes, left)
        right_idx = bin_search(primes, 0, len_primes, right)

        for x in primes[left_idx:right_idx+1]:
            if (x + 1) // 2 in primes_set:
                output += 1

        print(output)
    # return output


main()
# print(main())

Submission status: Time Limit Exceeded

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

a = [i for i in range (2, 100001)]
p = []
while True:
    prime = a[0]
    if prime > math.sqrt(100000):
        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)

ans = [0]*100001
for i in p:
    if i==2:
        continue
    if (i+1)//2 in p:
        ans[i] = 1
        
for i in range(1,100001):
    ans[i] += ans[i-1]

for a,b in l:
    print(ans[b]-ans[a-1])

Submission status: Time Limit Exceeded

Solution code:
def prime_list(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))
	return list(primes)

q = int(input())
primes = prime_list(10**5)

for i in range(q):
	l, r = map(int, input().split())
	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:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

q = int(input())
list_Q = [ list(map(int,input().split(" "))) for i in range(q)]

num = pow(10,5)
list_PRE = [0]*(2*num+10)
list_PRE[2] = 1
for i in range(1, 2*num+10, 2):
    if len(prime_factorize(i)) == 1:
        list_PRE[i] = 1

list_2017 = [0]*(2*num+10)
for i in range(1, num+1, 2):
    if list_PRE[i] == 1 and list_PRE[(i+1)//2] == 1:
        list_2017[i] = 1

for i, j in list_Q:
    print(sum(list_2017[i:j+1]))

Submission status: Time Limit Exceeded

Solution code:
def prime(x):
    for i in range(2, int(x**0.5+1)):
        if x % i == 0:
            return False
    return True
q = int(input())
l, r = [], []
for _ in range(q):
    l_, r_ = map(int, input().split())
    l.append(l_)
    r.append(r_)
mi, ma = min(l), max(r)
if mi == 1: mi += 2
p = [0 for _ in range(ma)]
for i in range(mi, ma+1, 2):
    if prime(i) and prime((i+1)//2):
        p[i-1] = 1
for i in range(q):
    print(sum(p[l[i]-1:r[i]]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import itertools
import random

def is_prime(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

A =[0] * 10**5
for i in range(10**5):
    if i%2 == 1:
        if is_prime(i) == True and is_prime((i+1)//2) == True:
            A[i] = 1
B = list(itertools.accumulate(A))
B = [0] + B

Q = int(input())
for i in range(Q):
    a, b = map(int,input().split())
    print(B[b+1]-B[a])

Submission status: Time Limit Exceeded

Solution code:

import math


def query(ql, qr, buckets, is_prime):
    ans = 0
    lb, rb = -1, -1
    for st, ed, count in buckets:
        # 完全に含まれていればそのままカウント
        if ql < st and ed < qr:
            ans += count
            continue
        
        # 左にはみ出している
        if st < ql <= ed and ed <= qr:
            for x in range(ql, ed + 1):
                ans += x % 2 and is_prime[x] and is_prime[(x + 1) // 2]
            continue

        # 右にはみ出している
        if ql < st and st <= qr < ed:
            for x in range(st, qr + 1):
                ans += x % 2 and is_prime[x] and is_prime[(x + 1) // 2]
            continue

        # 収まっている
        if st <= ql and qr <= ed:
            for x in range(ql, qr + 1):
                ans += x % 2 and is_prime[x] and is_prime[(x + 1) // 2]
            break
    return ans
        

def submit():
    n_max = 10**5

    # n_maxまでの素数を数える
    is_prime = {x: True for x in range(1, n_max + 1)}
    is_prime[1] = False
    for x in range(2, math.ceil(math.sqrt(n_max)) + 1):
        if is_prime[x]:
            y = 2 * x
            while y <= n_max:
                is_prime[y] = False
                y += x
    
    # バケット法で数えておく
    bucket_size = math.floor(math.sqrt(n_max))
    buckets = []
    for st in range(1, n_max + 1, bucket_size):
        ed = st + bucket_size - 1
        like2017s = [is_prime[x] and is_prime[(x + 1) // 2] for x in range(st, ed + 1) if x % 2 and x <= n_max]
        bucket_count = sum(like2017s)
        buckets.append([st, ed, bucket_count])
    
    # クエリを処理する
    q = int(input())
    queries = []
    for _ in range(q):
        queries.append(list(map(int, input().split())))
        
    for q in queries:
        res = query(q[0], q[1], buckets, is_prime)
        print(res)


submit()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
b = [0,0,0]
def judge(n):
    if  n!= 1 and all(n%i != 0 for i in range(2,round(n**(1/2) +1))):
        return True
    else:
        return False
for i in range(3,10**5):
    if judge(i) and judge((i+1)/2):
        b.append(1)
    else:
        b.append(0)
for i in range(n):
    print(sum(b[a[i][0]:a[i][1]+1]))

Submission status: Time Limit Exceeded

Solution code:
def trial_division(n):
    prime_factors = list()
    while n % 2 == 0:
        prime_factors.append(2)
        n //= 2
    p = 3
    while p * p <= n:
        if n % p == 0:
            prime_factors.append(p)
            n //= p
        else:
            p += 2
    if n != 1:
        prime_factors.append(n)
    return prime_factors

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

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

num = [i for i in range(2,10**5+1)]
so = []
while len(num):
  i = num[0]
  so.append(i)
  num = [j for j in num if j%i!=0]

import bisect

like2017 = []
for sos in so:
  l_idx = bisect.bisect_left(so, (sos+1)//2)
  if l_idx>=len(so) or sos%2==0:continue
  if so[l_idx]==(sos+1)//2:
    like2017.append(sos)
#print(like2017[:20])  

for _ in range(q):
  ans = 0
  l, r = map(int, input().split())
  l_idx = bisect.bisect_left(like2017, l)
  r_idx = bisect.bisect_right(like2017, r)
  #print(l_idx, r_idx)
  ans = r_idx-l_idx
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - 2017-like Number
# https://atcoder.jp/contests/abc084/tasks/abc084_d

prime = []
is_prime = []
is_prime.append(False)
is_prime.append(False)

def sieve(r):
    for i in range(2, r + 1):
        is_prime.append(True)

    for i in range(2, r + 1):
        if is_prime[i]:
            prime.append(i)

            j = 2 * i
            while j <= r:
                is_prime[j] = False
                j = j + i

def main():
    Q = int(input())
    querys = []
    max_r = 0
    for i in range(Q):
        l, r = map(int, input().split())
        querys.append((l, r))
        if max_r < r:
            max_r = r

    sieve(max_r)

    for l, r in querys:
        like_numbers = [n for n in prime if n % 2 == 1 and l <= n <= r and is_prime[(n + 1) // 2]]
        print(len(like_numbers))
    
main()

Submission status: Time Limit Exceeded

Solution code:
# D - 2017-like Number
# https://atcoder.jp/contests/abc084/tasks/abc084_d

prime = []
is_prime = []
is_prime.append(False)
is_prime.append(False)

def sieve(r):
    start = len(is_prime)
    if start >= r:
        return 

    for i in range(start, r + 1):
        is_prime.append(True)

    for i in prime:
        j = 2 * i
        while j <= r:
            if j < start:
                j = j + i
                continue

            is_prime[j] = False
            j = j + i

    for i in range(start, r + 1):
        if is_prime[i]:
            prime.append(i)

            j = 2 * i
            while j <= r:
                is_prime[j] = False
                j = j + i

def main():
    # answers = []
    Q = int(input())
    querys = []
    max_r = 0
    for i in range(Q):
        l, r = map(int, input().split())
        querys.append((l, r))
        if max_r < r:
            max_r = r

    sieve(max_r)

    for l, r in querys:
        like_numbers = [n for n in prime if n % 2 == 1 and l <= n <= r and is_prime[(n + 1) // 2]]
        # answers.append(len(like_numbers))
        print(len(like_numbers))
    
    # for answer in answers:
    #     print(answer)

main()