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:
# https://atcoder.jp/contests/abc084/tasks/abc084_d

Nmax = 10**6 //2 + 1

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

cum = [0]*(Nmax+1)

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

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

Submission status: Time Limit Exceeded

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

Nmax = 10**6 + 1

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

cum = [0]*Nmax

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

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

Submission status: Time Limit Exceeded

Solution code:
def calc_prime(n):
    primes = set([2, 3, 5])
    for x in range(7, n + 1, 2):
        is_p = True
        for p in primes:
            if x % p == 0:
                #print(x, p)
                is_p = False
                break

        if is_p:
            primes.add(x)

    return primes
    

def main():
    q = int(input())
    range_set = []
    mx = 0
    for _ in range(q):
        l, r = [int(x) for x in input().split()]
        mx = max(mx, r)
        range_set.append((l, r))

    primes = calc_prime(mx)
    #print(primes)
    for l, r in range_set:
        #print(l, r)
        c = 0
        for x in range(l, r + 1, 2):
            if x in primes and (x + 1) / 2 in primes:
                c += 1

        print(c)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    # エラトステネスの篩で、
    # 2 から 10^5までの素数を列挙
    limit = 10 ** 5 + 1
    prime = [False if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 else True for n in range(limit)]
    prime[0] = prime[1] = False
    prime[2] = prime[3] = prime[5] = True
    for p in range(3, limit, 2):
        if math.sqrt(limit) < p:
            break
        for q in range(p ** 2, limit, p):
            prime[q] = False

    # 回答
    Q = ii()
    for q in range(Q):
        l, r = il()
        ret = 0
        for t in range(l, r + 1):
            if prime[t] and prime[(t + 1) // 2]:
                ret += 1
        print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
MAX = 10**5
N = [0]*MAX

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

n = int(input())
sosuu = eratosthenes(MAX)

total = 0
mae = sosuu[0]
for s in sosuu:
    for i in range(mae,s):
        N[i] = total
    if (s+1) // 2 in sosuu:
        total += 1
    mae = s

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.buffer.readline
Q = int(input())


def is_prime(v):
    for i in range(2, v):
        if i * i > v:
            break
        if v % i == 0:
            return False
    return True


is_primes = np.ones(10**5 + 2, dtype='bool')
is_primes[:2] = False
for i in np.arange(2, is_primes.shape[0]):
    if not is_primes[i]:
        continue
    if is_prime(i):
        is_primes[i * 2::i] = False
# print('is_primes', is_primes[:14])

V = [0] * (10**5 + 2)
for i in range(1, len(V)):
    if i % 2 == 0:
        V[i] = V[i - 1]
        continue
    if is_primes[i] and is_primes[(i + 1) // 2]:
        V[i] = V[i - 1] + 1
    else:
        V[i] = V[i - 1]
# print('V', V)

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = 10**5
Q = int(input())

lst1 = [2]
for L in range(3, N, 2):
    if all(L % L2 != 0 for L2 in lst1):
        lst1.append(L)

lst1 = set(lst1) 
lst2 = [i for i in lst1 if (i+1)//2 in lst1]

lst2.sort()

for _ in range(Q):
  l, r = map(int, input().split())
  a = bisect.bisect_left(lst2, l)
  b = bisect.bisect_right(lst2, r)
  print(b-a)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = 10**5
Q = int(input())

lst1 = [2]
for L in range(3, N, 2):
    if all(L % L2 != 0 for L2 in lst1):
        lst1.append(L)

lst2 = [i for i in lst1 if (i+1)//2 in lst1]

lst2.sort()

for _ in range(Q):
  l, r = map(int, input().split())
  a = bisect.bisect_left(lst2, l)
  b = bisect.bisect_right(lst2, r)
  print(b-a)

Submission status: Time Limit Exceeded

Solution code:
import sys

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))

n  = ri()
lq = [rl() for _ in range(n)]
dp = [-1] * (10**5+1)
def is_prime(x):
    if x == 1:
        return False
    else:
        for i in range(3, int(x*0.5)+1, 2):
            if x % i == 0:
                return False
        else:
            x = (x+1)//2
            for i in range(2, int(x*0.5)+1):
                if x % i == 0:
                    return False
            else:
                return True

for li in lq:
    l, q = li
    cnt = 0
    for i in range(l, q+1, 2):
        if dp[i] == 0:
            continue
        elif dp[i] == 1:
            cnt += 1
            continue
        elif is_prime(i):
            dp[i] = 1
            cnt += 1
            continue
        else:
            dp[i] = 0
            continue
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))

n  = ri()
lq = [rl() for _ in range(n)]
dp = [-1] * (10**5+1)
def is_prime(x):
    if x == 1:
        return False
    else:
        for i in range(3, int(x*0.5)+1, 2):
            if x % i == 0:
                return False
        else:
            x = (x+1)//2
            for i in range(2, int(x*0.5)+1):
                if x % i == 0:
                    return False
            else:
                return True

for li in lq:
    l, q = li
    cnt = 0
    for i in range(l, q+1, 2):
        if dp[i] == 0:
            continue
        elif dp[i] == 1:
            cnt += 1
            continue
        elif is_prime(i):
            dp[i] = 1
            cnt += 1
            continue
        else:
            dp[i] = 0
            continue
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))

n  = ri()
l = []
q = []
for _ in range(n):
    l1, q1 = rm()
    l.append(l1)
    q.append(q1)

ma = max(q)
mi = min(l)
li = [0] * (ma+1)
for i in range(mi, ma+1, 2):
    if i == 1:
        continue
    for k in range(2, int(i**0.5)+1):
        if i % k == 0:
            break
    else:
        a = i
        i = (i+1)//2
        for k in range(2, int(i**0.5)+1):
            if i % k == 0:
                break
        else:
            li[a] = 1
for l2, q2 in zip(l, q):
    print(sum(li[l2: q2+1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

q = int(input())

# 素数列挙
n = 10**5 + 1
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))

arr = np.array(list(primes))
arr = np.bincount(arr)

# 素数かつ2017に似た数を列挙
like_2017 = np.zeros(n, bool)
for i in np.where(arr == 1)[0]:
    if (i + 1) // 2 in primes:
        like_2017[i] = True


def cnt_primes(l, r):
    return like_2017[l:r + 1].sum()


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    tmp += cnt_primes(l, r)
    ans.append(tmp)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import math

q = int(input())


n = 100000
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)


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    for i in range(l, r + 1, 2):
        tmp += i in primes and (i + 1) // 2 in primes
    ans.append(tmp)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import math

q = int(input())


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


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    for i in range(l, r + 1, 2):
        tmp += int(is_prime(i) and is_prime((i + 1) // 2))
    ans.append(tmp)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
def l(): return list(map(int, input().split()))
def m(): return map(int, input().split())

def sieve(n): # エラトステネスの篩ですよ
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return [i for i in range(2,n) if num[i]]

def main():
  q = int(input())
  for i in range(q):
    l, r = m()
    prime = sieve(r+1)
    # print(prime)
    likp = [0]*r
    for i in prime:
      if (i+1) // 2 in prime:
        likp[i-1] = 1
    # print(likp)
    sm = [0]*(r+1)
    for i in range(r):
      sm[i+1] = sm[i] + likp[i]
    # print(sm)
    print(sm[r] - sm[l-1])
   


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def l(): return list(map(int, input().split()))
def m(): return map(int, input().split())
def sieve(n):
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return [i for i in range(2,n) if num[i]]

def main():
  q = int(input())
  for i in range(q):
    l, r = m()
    prime = sieve(r+1)
    cnt = 0
    for j in range(l, r+1):
      if j in prime:
        if (j+1) // 2 in prime:
          cnt += 1
    print(cnt)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())
sosu = [2]

for L in range(3, 10**5, 2): # 2 以外の素数は奇数なので
    for L2 in sosu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosu.append(L)

sosu = set(sosu)
li = []
for i in range(Q):
    l, r = map(int, input().split())
    li.append((l, r))

for l,r in li:
    ans = 0
    for x in range(l, r+1):
        if x % 2 == 1:
            if x in sosu and (x+1)/2 in sosu:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())
sosu = set([2])

for L in range(3, 10**5, 2): # 2 以外の素数は奇数なので
    for L2 in sosu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosu.add(L)


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

for l,r in li:
    ans = 0
    for x in range(l, r+1):
        if x % 2 == 1:
            if x in sosu and (x+1)/2 in sosu:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())
sosu = [2]

for L in range(3, 10**5, 2): # 2 以外の素数は奇数なので
    for L2 in sosu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosu.append(L)


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

for l,r in li:
    ans = 0
    for x in range(l, r+1):
        if x % 2 == 1:
            if x in sosu and (x+1)/2 in sosu:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())

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

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

for l,r in li:
    ans = 0
    for x in range(l, r+1):
        if x % 2 == 1:
            if is_prime(x) and is_prime((x+1)/2):
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate

    q, *lr = map(int, open(0).read().split())
    l, r = min(lr[::2]), max(lr[1::2])

    p = []
    *n, = range(2, r + 1)

    while n:
        x = n[0]
        p.append(x)
        *n, = filter(lambda m: m % x != 0, n)
    q = set(p)
    a = [0] * (r + 1)
    for x in p[::-1]:
        x = p.pop()
        if (x + 1) // 2 in q:
            a[x] += 1

    *b, = accumulate(a)
    for p, q in zip(*[iter(lr)] * 2):
        print(b[q] - b[p - 1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate

    q, *lr = map(int, open(0).read().split())
    l, r = min(lr[::2]), max(lr[1::2])

    p = []
    *n, = range(2, r + 1)

    while n:
        x = n[0]
        p.append(x)
        *n, = filter(lambda m: m % x != 0, n)

    a = [0] * (r + 1)
    for x in p[::-1]:
        x = p.pop()
        if (x + 1) // 2 in p:
            a[x] += 1

    *b, = accumulate(a)
    for p, q in zip(*[iter(lr)] * 2):
        print(b[q] - b[p - 1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
import heapq
import time

start = time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
q = ri()
lr = [rl() for _ in range(q)]

def Is_prime(n):
    if n<2:return False
    elif n==2:return True
    elif n>3 and n%2==0:return False
    for i in range(3, n):
        if i*i>n:
            break
        if n%i==0:return False
    return True

for j in lr:
    ans=0
    for i in range(j[0], j[1]+1):
        if i%2==0:continue
        if Is_prime(i) and Is_prime((i+1)//2):ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    if left % 2 == 0:
        left += 1
    print(len([n for n in range(left, right + 1, 2) if is_prime(n) and is_prime((n + 1) // 2)]))

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    if left % 2 == 0:
        left += 1
    print(len([n for n in range(left, right + 1, 2) if is_prime(n) and is_prime((n + 1) // 2)]))

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
from math import floor,sqrt
def isPrime(x):
  if x<2:
    return False
  elif x==2:
    return True
  elif x%2==0:
    return False
  for i in range(3,floor(sqrt(x))+1,2):
    if x%i==0:
      return False
  return True
def PrimeSet(x):
  p=set()
  for i in range(1,x+1):
    if isPrime(i):
      p.add(i)
  return p
prime1=PrimeSet(10**5)
prime2=set()
for j in range(1,10**5+1):
  if j%2:
    i=(j+1)//2
    if isPrime(i):
      prime2.add(j)
prime3=prime1&prime2
for i in range(q):
  l,r=map(int,input().split())
  print(len(set(range(l,r+1))&prime3))

Submission status: Time Limit Exceeded

Solution code:
N = 10**5
bit_prime = 0
bit_2017 = [0] * N


def pre_make_prime():
    global bit_prime
    bit_prime = (2 ** N - 1) ^ 3
    for i in range(2, N + 1):
        if (bit_prime >> i) & 1:
            for j in range(i * 2, N + 1, i):
                bit_prime &= ~(1 << j)


def pre_make_2017():
    global bit_2017
    for i in range(3, N, 2):
        if is_prime(i) and is_prime((i + 1) // 2):
            bit_2017[i] = 1


def is_prime(n):
    return bit_prime & (1 << n)


def resolve():
    pre_make_prime()
    pre_make_2017()
    global bit_2017
    Q = int(input())
    for _ in range(Q):
        L, R = [int(i) for i in input().split()]
        print(sum(bit_2017[L:R + 1]))


resolve()

Submission status: Time Limit Exceeded

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

n = 10**5
#primes = set(range(3, n+1, 2))|set([2])
primes = set(range(3, n+1, 2)) #偶数は除く
for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*3, n+1, i*2))
primes = list(primes)

Likes = [0] * (n+1)
cnt = 0
for i in primes:
    if (i+1)//2 in primes or (i+1)//2==2:
        Likes[i]=1
for i in range(1,n):
    Likes[i]+=Likes[i-1]

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
q = int(input())


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


for _ in range(q):
    l, r = map(int, input().split())
    count = 0
    prime_list = primes(r+1)
    #print(prime_list)
    for p in prime_list:
        if p >= l:
            pp = (p+1)//2
            if pp in prime_list:
                count += 1
    print(count)

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


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

Submission status: Time Limit Exceeded

Solution code:
n = 10**5
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

is_simular_2017 = is_prime.copy()

for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if not is_prime[(i + 1) // 2]:
            is_simular_2017[i] = False


simular_2017 = [i for i in range(len(is_simular_2017)) if is_simular_2017[i]]


Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
for l, r in LR:
    count = 0
    for s in simular_2017:
        if l <= s <= r:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

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

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

x_list = [0] * (10 ** 5)
for i in range(1, 10**5, 2):
    if like(i):
        x_list[i] = 1

for i in range(Q):
    print(sum(x_list[l_r[i][0]: l_r[i][1]+1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

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):
        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]]
n = 10**5+1
a = set(sorted(primes(n)))
q = int(input())
for i in range(q):
    cnt = 0
    l,r = map(int,input().split())
    for j in range(l,r+1):
        s = j
        t = (j+1)//2
        if s in a and t in a:
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

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

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

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
M = 10**6
p = [1 for i in range(M+1)]
p[0] = 0
p[1] = 0
for x in range(2, int(sqrt(M))+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0

a = [0 for i in range(M+1)]
for i in range(M):
    if i%2 != 0 and p[i] and p[(i+1)//2]:
        a[i] = 1

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

Submission status: Time Limit Exceeded

Solution code:

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

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


for i, j in S_list:
    cnt = 0
    for n in range(i, j+1, 2):
        if isprime(n) and isprime((n+1)/2):
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

def primes(n):
    isp = [True for _ in range(n+1)]
    isp[0] = False
    isp[1] = False
    l = floor(sqrt(n))
    n += 1
    for i in range(4, n, 2):
        isp[i] = False
    for i in range(3, l, 2):
        if not isp[i]:
            continue
        for j in range(i*2, n, i):
            isp[j] = False
    return isp

q = int(input())
maxv = 10**5
isp = primes(maxv)
for _ in range(q):
    l, r = map(int, input().split())
    ans = 0
    for i in range(l, r+1):
        if isp[i] and isp[(i+1)//2]:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

def isp(x):
    if x == 1:
        return False
    elif x == 2:
        return True
    elif not x & 1:
        return False
    maxv = floor(sqrt(x))+1
    for i in range(3, maxv+1, 2):
        if x % i == 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 isp(i) and isp((i+1)//2):ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

N = int(1e+5)
max_num = int(N**0.5)
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2,max_num+1):
    if not is_prime[i]:
        continue
    for j in range(i*2,N+1,i):
        is_prime[j] = False

ans = [False] * (N+1)
for i in range(3,N+1,2):
    b = (i+1)//2
    if is_prime[i] and is_prime[b]:
        ans[i] = True

for l,r in query:
    print(ans[l:r+1].count(True))