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: Accepted

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


def Eratosthenes(n):
    """n(>=6)未満の素数列挙 """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(sqrt(n)) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * ((n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
    s = [False] * n
    for i in range(1, n // 3 - correction):
        if sieve[i]:
            s[3 * i + 1 | 1] = True
    s[2] = True
    s[3] = True
    return s


sieve = Eratosthenes(10 ** 5 + 1)
ans = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    if sieve[i] and sieve[(i + 1) // 2]:
        ans[i] += 1
for i in range(3, 10 ** 5):
    ans[i + 1] += ans[i]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l - 1])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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

a = [0] * (10 ** 5 + 5)
for i in range(1, 10**5+1):
    a[i] = a[i-1]
    if is_prime(i) and is_prime((i+1) // 2):
        a[i] += 1
Q = ni()
for i in range(Q):
    l, r = na()
    print(a[r] - a[l-1])

Submission status: Accepted

Solution code:
import numpy as np
def eratosthenes(m):
    if m<2:
        return []
    dp=[True]*(m+1)
    sosu=[2]
    like=[0]*(m+1)#累積和
    like[3]=1
    for x in range(3,m+1,2):
        if dp[x]:
            sosu.append(x)
            if dp[(x+1)//2]==True and (x+1)//2%2==1:
                like[x]+=1
        for j in range(2*x, m+1, x):
            dp[j]=False
    return like

like=eratosthenes(10**5+1)
c = np.array(like).cumsum()
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    ans=c[r]-c[l-1]
    print(ans)

Submission status: Accepted

Solution code:
from itertools import *

MAX=10**5+1
is_prime=[True]*MAX
is_prime[0]=False
is_prime[1]=False
for i in range(2,MAX):
  if is_prime[i]==False:
    continue
  for j in range(i*2,MAX,i):
    is_prime[j]=False

a=[0]*MAX
for i in range(MAX):
  if i%2==0:
    continue
  if is_prime[i] and is_prime[(i+1)//2]:
    a[i]=1

s=[0]+list(accumulate(a))

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

Submission status: Accepted

Solution code:
def prime_factor_table(n):
    table = [0] * (n + 1)

    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i

    return table

l = prime_factor_table(100000)
l[0] = 1
l[1] = 1
l2 = [0]*100000

for i in range(1,100000,2):
    x = (i+1)//2
    if l[i] == 0 and l[x] == 0:
        l2[i] = 1

l3 = [0]
for i in range(100000):
    x = l3[i] + l2[i]
    l3.append(x)

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

Submission status: Accepted

Solution code:
import math
import bisect
def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

l = get_prime(100000)
l2 = []
for i in range(len(l)):
    x = l[i]
    y = (x+1)//2
    if y in l:
        l2.append(x)
        
Q = int(input())
for i in range(Q):
    a,b = map(int, input().split())
    x = bisect.bisect_left(l2, a)
    y = bisect.bisect_right(l2, b)
    print(y-x)

Submission status: Accepted

Solution code:
import numpy as np
from math import sqrt

def main():
    with open(0) as f:
        Q = int(f.readline())
        Query = [tuple(map(int, line.split())) for line in f.readlines()]
    
    p_table = makePtable(10**5)
    p_set = set(p_table)
    Like2017 = [p for p in p_table if (p+1)//2 in p_set]
    #データベースを累積和で作成
    database = np.array([0] * (10**5+1))
    for i in Like2017:database[i] = 1
    database = database.cumsum(axis=0)
    
    for l,r in Query:
        print(database[r+1] - database[l-1])

def makePtable(N):
    table = list(range(2,N+1))
    result = []
    p = 2
    while p < sqrt(N):
        p = table[0]
        result.append(p)
        table = [x for x in table if x % p != 0]
    return result + table

main()

Submission status: Accepted

Solution code:
import bisect
q=int(input())

def sieve(n):
      is_prime = [True for _ in range(n)]
      is_prime[0] = False
  
      for i in range(2, int((n**0.5)//1+2)):
          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] and is_prime[i//2]]
      return table[1:]

x=sieve(10**5+1)
ans=[]

for _ in range(q):
  l,r=map(int,input().split())
  ans.append(bisect.bisect_right(x,r)-bisect.bisect_left(x,l))

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

Submission status: Accepted

Solution code:
Q = int(input())

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

max_num = 0
for _, r in queries:
    max_num = max(max_num, r)


is_prime = [True] * (max_num + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, max_num + 1):
    if not is_prime[i]:
        continue

    cnt = 2
    while i * cnt <= max_num:
        is_prime[i * cnt] = False
        cnt += 1

nums_like = [0] * (max_num + 1)
cnt = 0
for i in range(1, max_num + 1):
    if i % 2 == 0:
        nums_like[i] = nums_like[i - 1]
    else:
        if is_prime[i] and is_prime[(i + 1) // 2]:
            cnt += 1

        nums_like[i] = cnt


for l, r in queries:
    print(nums_like[r] - nums_like[l - 1])

Submission status: Accepted

Solution code:
import bisect
q=int(input())
ans=[]

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

    for i in range(2, int((n**0.5)//1+2)):
        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] and is_prime[i//2]]
    return table

l_2017=sieve(10**5+1)[1:]

for i in range(q):
    l,r=map(int,input().split())
    ans.append(bisect.bisect_right(l_2017,r)-bisect.bisect_left(l_2017,l))

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

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N=10**5
p=[1]*(N+1)
p[0]=p[1]=0
q=[0]*(N+1)
for i in range(2,N+1):
    if p[i]==1:
        tmp=2*i
        while tmp<=N:
            p[tmp]=0
            tmp+=i
    if i%2!=0 and p[i]==1 and p[(i+1)//2]==1:
        q[i]=q[i-1]+1
    else:
        q[i]=q[i-1]
Q=intput()
for _ in range(Q):
    l,r=mint()
    print(q[r]-q[l-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
from itertools import accumulate

import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


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]


max_ = pow(10, 5) + 2
primes = get_sieve_of_eratosthenes(max_)
num_lile2017 = [0]*max_
primes2 = []
for prime in primes:
    primes2.append(2*prime-1)
like2017 = sorted(list(set(primes2) & set(primes)))
for i in range(3, max_, 2):
    if (i in like2017):
        num_lile2017[i] = 1
num_lile2017 = list(accumulate(num_lile2017))
# print(num_lile2017)

Q = z()
for i in range(Q):
    l, r = zz()
    print(num_lile2017[r] - num_lile2017[l-1])

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

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

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

similars=[0]*MAX
for i in range(2,MAX):
  if i in primes and (i+1)//2 in primes:
    similars[i]=1
similars=list(accumulate(similars))

for i in lr:
  l,r=i
  print(similars[r]-similars[l-1])

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def gen_prime_table(last: int, first=2) -> list:
    if last < 1:
        return [False]
    elif last < 2:
        return [False, False]
    primes = []
    table = [True] * (last + 1)
    table[0] = False
    table[1] = False

    for i in range(first, last + 1):
        if table[i]:
            primes.append(i)
            for j in range(i * 2, last + 1, i):
                table[j] = False
    return table


def main():
    q = input_int()
    prime_table = gen_prime_table(10**5 + 1)
    prime_cusum = [0] * (10**5 + 1)
    for i in range(1, 10**5):
        if prime_table[i] and prime_table[(i + 1) // 2]:
            prime_cusum[i] = prime_cusum[i - 1] + 1
        else:
            prime_cusum[i] = prime_cusum[i - 1]

    for _ in range(q):
        l, r = input_int_list()
        print(prime_cusum[r] - prime_cusum[l - 1])

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Q = int(input())

S = [0]*100010
for i in range(3,100010,2):
    S[i] += S[i-2]
    if is_prime(i) and is_prime((i+1)//2):
        S[i] += 1

for q in range(Q):
    l, r = map(int,input().split())
    print(S[r] - S[max(0,l-2)])

Submission status: Accepted

Solution code:
Q = int(input())

is_prime = [True] * 100010
for i in range(100010):
    if i <= 1:
        is_prime[i] = False
        continue

    if is_prime[i]:
        for j in range(2*i,100010,i):
            is_prime[j] = False

is_2017like_prime = [False] * 100010
for i in range(1,100010,2):
    if is_prime[i] & is_prime[(i+1)//2]:
        is_2017like_prime[i] = True

cumsum = [0]
for a in is_2017like_prime[1:]:
    cumsum.append(cumsum[-1] + a)

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

Submission status: Accepted

Solution code:
Q = int(input())

N=10**5
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]]

F = primes(N)
F_2007=[]

a = [0]*(N+1)

for f in F:
    a[f] = 1

for f in F:
    if a[(f+1)//2] == 1:
        F_2007.append(f)
        
a = [0]*(N+1)
for f in F_2007:
    a[f] = 1
    
a_sum = [0]
for a_ in a:
    a_sum.append(a_sum[-1]+a_)
a_sum=a_sum[1:]

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

Submission status: Accepted

Solution code:
Q = int(input())

lim = 10**5+10
p = [True]*lim
p[0] = False
p[1] = False
for i in range(2, int(lim**0.5)+1):
    for j in range(i*2, 10**5+1, i):
        p[j] = False

y = [0]*lim
for i in range(3, lim, 2):
    y[i] = y[i-2]
    if p[i] and p[(i+1)//2]:
        y[i] += 1
    y[i-1] = y[i-2]

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

Submission status: Accepted

Solution code:
q=int(input())

#prime table
prime=[0 for i in range(10**5+5)]
for i in range(2,10**5+5):
  j=1
  if not prime[i]:
    while j*i<=10**5+4:
      prime[j*i]=i
      j+=1

like2017=[0 for i in range(10**5+5)]
for i in range(3,10**5+5,2):
  j=(i+1)//2
  if i==prime[i] and j==prime[j]:
    like2017[i]=1

like2017sum=[0 for i in range(10**5+5)]
for i in range(10**5+4):
  like2017sum[i+1]=like2017sum[i]+like2017[i+1]
#print(like2017[0:54])
#print(like2017sum[0:80])
for i in range(q):
  l,r=map(int,input().split())
  if like2017[l]==1:
    alpha=1
  else:
    alpha=0
  print(like2017sum[r]-like2017sum[l]+alpha)

Submission status: Accepted

Solution code:
q = int(input())
n = 10**5
nums = [False]*2+[True]*(n-2)
ans = [0]*n
for i in range(2, n):
    if nums[i]:
        for j in range(i*2, n, i):
            nums[j] = False
pre = 0
for i in range(3, n, 2):
    if nums[i] and nums[(i+1)//2]:
        ans[i] += pre+1
        pre = ans[i]
    else:
        ans[i] = pre
for _ in range(q):
    l, r = map(int, input().split())
    print(ans[r]-ans[max(l-2, 1)])

Submission status: Accepted

Solution code:
MAX=101010
is_prime=[True]*MAX
is_prime[0]=False
is_prime[1]=False
for i in range(2,MAX):
  if is_prime[i]==False:
    continue
  for j in range(i*2,MAX,i):
    is_prime[j]=False

a=[0]*MAX
for i in range(MAX):
  if i%2==0:
    continue
  if is_prime[i] and is_prime[(i+1)//2]:
    a[i]=1

s=[0]
for x in a:
  s.append(s[-1]+x)

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

Submission status: Accepted

Solution code:
from math import sqrt
import bisect


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

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

    return True


def solve(query):
    ans = []
    al = []
    for i in range(3, 10**5+1, 2):
        if is_prime(i) and is_prime((i+1)//2):
            al.append(i)

    for q in query:
        if is_prime(q[0]) and is_prime((q[0]+1)//2):
            l_ind = bisect.bisect_right(al, q[0]) - 1
        else:
            l_ind = bisect.bisect_right(al, q[0])
        if is_prime(q[1]) and is_prime((q[1]+1)//2):
            r_ind = bisect.bisect_left(al, q[1])
        else:
            r_ind = bisect.bisect_left(al, q[1]) - 1
        ans.append(r_ind-l_ind+1)

    return ans


if __name__ == "__main__":
    Q = int(input())
    query = [list(map(int, input().split())) for _ in range(Q)]

    ans = solve(query)

    for a in ans:
        print(a)

Submission status: Accepted

Solution code:
import math

def main():
	prime = [2, 3, 5, 7]
	for n in range(11, 100001):
		for p in prime:
			if n % p == 0:
				break
			if p > math.sqrt(n):
				prime.append(n)
				break
	sim = []
	j = 0
	for i in range(1, len(prime)):
		p = prime[i]
		q = int((p + 1) / 2)
		while q > prime[j]:
			j += 1
		else:
			if q == prime[j]:
				sim.append(p)
	sim.append(12345678)

	sim_n = [0]
	k = 0
	for s in range(1, 100001):
		if s == sim[k]:
			sim_n.append(sim_n[-1] + 1)
			k += 1
		else:
			sim_n.append(sim_n[-1])

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

main()

Submission status: Accepted

Solution code:
# nまでの自然数が素数かどうかを表すリストを返す
def makePrimeChecker(n):
	isPrime = [True] * (n + 1)
	isPrime[0] = False
	isPrime[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if isPrime[i]:
			for j in range(i * i, n + 1, i):
				isPrime[j] = False
	return isPrime



isPrime = makePrimeChecker(100000)
Q = int(input())
L=[0]

#2017nunberの累積和
for i in range(1, 100000):
	if i&1==1 and isPrime[i] and isPrime[(i+1)//2]:
		L.append(L[-1]+1)
	else:
		L.append(L[-1])

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

Submission status: Accepted

Solution code:
# nまでの自然数が素数かどうかを表すリストを返す
def makePrimeChecker(n):
	isPrime = [True] * (n + 1)
	isPrime[0] = False
	isPrime[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if isPrime[i]:
			for j in range(i * i, n + 1, i):
				isPrime[j] = False
	return isPrime




#2017nunberの累積和
Q = int(input())
L = [0]
isPrime = makePrimeChecker(100000)
for i in range(1, 100000):
    if i&1==1 and isPrime[i] and isPrime[(i+1)//2]:
        L.append(L[-1] + 1)
    else:
        L.append(L[-1])
for i in range(Q):
    l, r = map(int, input().split())
    print(L[r] - L[l-1])

Submission status: Accepted

Solution code:
import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

MaxQ = 10**5+1
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

a = [0]*MaxQ
s = [0]*MaxQ
prime = isPrime_np(MaxQ)
pset = set(prime)
for p in prime:
    if (p+1)/2 in pset:
        a[p] = 1

ans = []
s = np.cumsum(a)
    
for l,r in lr:
    ans.append(s[r] - s[l-1])
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

MaxQ = 10**5+1
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

a = [0]*MaxQ
s = [0]*MaxQ
prime = isPrime_np(MaxQ)
pset = set(prime)
for p in prime:
    if (p+1)/2 in pset:
        a[p] = 1

ans = []
for i in range(MaxQ-1):
    s[i+1] = s[i] + a[i]
    
for l,r in lr:
    ans.append(s[r+1] - s[l])
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
n_max = 10 ** 5 + 10
sieve = [0, 0] + [1]*n_max
m = 2
while m * m <= n_max:
    if sieve[m]:
        for n in range(2*m, n_max, m):
            sieve[n] = 0
    m += 1

ok = [0]*n_max
cums = [0]
for n in range(n_max):
    if sieve[n] and sieve[(n+1)//2]:
        ok[n] = 1
    cums.append(cums[-1]+ok[n])

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

Submission status: Accepted

Solution code:
def sieve(n):
    from math import sqrt
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = is_prime[1] = False
    for i in range(int(sqrt(n))+1):
        if is_prime[i]:
            for k in range(2, n//i+1):
                is_prime[i*k] = False
    return is_prime

def is_like2017(n):
    for i in range(n+1):
        if is_primeL[i]:
            #print(i, (i+1)//2)
            if is_primeL[(i+1)//2]:
                is_likeL[i] = True

n = 100000
is_primeL = sieve(n)
is_likeL = [False for _ in range(n+1)]
is_like2017(n)

from itertools import accumulate

cumL = list(accumulate(is_likeL))
cumL[0] = 0

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

Submission status: Accepted

Solution code:
def prime_checker_range(n): #n未満の数の中で素数のものを全て出力(リスト型)
    ls = [i for i in range(2,n)]
    p = 0
    while True:
        new_ls = [j for j in ls if (j % ls[p] != 0) or (j <= ls[p])]
        ls = new_ls
        if ls[p]**2 >= max(ls):
            return ls
        else:
            p += 1
    return ls
def prime_checker(i): #素数かどうか判定
    if i == 1:
        return False
    else:
        for j in range(2,(int(i**0.5))+1):
            if i % j == 0:
                return False
            else:
                continue
        return True
q = int(input())
ls = [i for i in prime_checker_range(10**5+1) if prime_checker((i+1)//2)]
di = [0]*(10**5+1)
c = 1
for p in range(len(ls)):
    if p != len(ls)-1:
        for m in range(ls[p],ls[p+1]):
            di[m] = c
    else:
        for m in range(ls[p],10**5+1):
            di[m] = c
    c += 1
for k in range(q):
    l,r = map(int,input().split())
    print(di[r]-di[l-1])