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 itertools
q = int(input())
left = []
right = []
for _ in range(q):
    l, r = map(int, input().split())
    left.append(l)
    right.append(r)

def check(n):
    root = int(n ** 0.5)
    if n == 1:
        return False
    elif n == 2:
        return True
    for i in range(2, root + 2):
        if n % i == 0:
            return False
    return True

upper = max(right)
f = [0, 0]
for i in range(3, upper + 1):
    if i % 2 == 0:
        f.append(0)
    elif check(i) and check((i + 1) // 2):
        f.append(1)
    else:
        f.append(0)
cumsum = list(itertools.accumulate(f))
for l, r in zip(left, right):
    if l == 1:
        print(cumsum[r - 1])
    else:
        print(cumsum[r - 1] - cumsum[l - 2])

Submission status: Accepted

Solution code:
from itertools import accumulate

#素数リスト
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=set(primes)

numli = [0]*n
for i in range(n):
  if i in primes:
    if (i+1)//2 in primes:
      numli[i] = 1

numli = list(accumulate(numli))

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

Submission status: Accepted

Solution code:
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
def prime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

number2017 = [0]+[0]*10**5
for i in range(3,10**5):
    if prime(i):
        if prime((i+1)//2):
            number2017[i]=1
import itertools
acc2017=list(itertools.accumulate(number2017))
for i in lr:
    print(acc2017[i[1]]-acc2017[i[0]-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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 set([i for i in range(n + 1) if is_prime[i]])
sosuu = primes(10**5*2+2)
lst=[0]*(10**5+1)
for i in range(10**5):
 if (i+1) in sosuu and int((i+2)/2) in sosuu and (i+1)!=2:
  lst[i+1]=lst[i]+1
 else:
  lst[i+1]=lst[i]
ans=0
Q=int(input())
for j in range(Q):
 l,r = map(int,input().split())
 print(lst[r]-lst[l-1])

Submission status: Accepted

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

Q = int(input())
my_max = 10 ** 5

nums = [i for i in range(2, my_max + 1)]
p = 2
idx = 0
while p * p <= my_max and idx < len(nums):
    nums = [n for n in nums if n % p != 0 or n == p]
    idx += 1
    p = nums[idx]
primes = set(nums)

ruiseki = [0]
total = 0
for i in range(1, my_max + 1):
    if i % 2 == 1 and i in primes and int((i + 1) / 2) in primes:
        total += 1
    ruiseki.append(total)

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

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect

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]}

p = primes(10**5)
kouho = []
for i in p:
    if (i+1)//2 in p:
        kouho.append(i)
kouho.sort()
q = int(input())
for i in range(q):
    l , r = map(int,input().split())
    s = bisect_left(kouho,l)
    t = bisect(kouho,r)
    print(t-s)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

q = ni()
lr = nan(q)

def ok(x):
    if x <= 1:
        return False
    i = 2
    flag1 = True
    while i * i <= x:
        if x % i == 0:
            flag1 = False
            break
        i += 1
    j = 2
    flag2 = True
    y = (x + 1) // 2
    while j * j <= y:
        if y % j == 0:
            flag2 = False
            break
        j += 1
    return flag1 and flag2

cu = [0] * (10 ** 5 + 7)
for i in range(1, 10 ** 5 + 7):
    cu[i] = cu[i - 1]
    if i % 2 != 0:
        cu[i] += ok(i)

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

Submission status: Accepted

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):
        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]], is_prime

primes_num, is_primes = primes(10**5+5)
sums = []
cnt = 0

for i in range(0, 10**5+4):
    if i % 2 != 0:
        a = (i+1) // 2
        if is_primes[i] and is_primes[a]:
            cnt += 1

    sums.append(cnt)

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

Submission status: Accepted

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

# 素数のリストを作る
sosus = {2: 0, 3: 0}
for i in range(5, N, 2):
    isSosu = True
    for j in range(3, int(math.sqrt(i))+1, 2):
        if i % j == 0:
            isSosu = False
            break
    if isSosu:
        sosus[i] = 0

#print(sosus)

# その数までに2017的な数が何個あるか管理する配列
ans = [0 for i in range(N)]
count = 0
for i in range(N):
    if i % 2 != 0:
        if i in sosus and (i+1)//2 in sosus:
            count += 1

    ans[i] = count


#print(ans[:15])

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

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter

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

rmax = max(lr, key=itemgetter(1))[1]
primes = list(range(rmax+1))
primes [1] = 0

for i in range(2, int(rmax**0.5)+ 2):
    for j in range(2 * i, rmax+1, i):
        primes[j] = 0
primess = [prime for prime in primes[:] if prime!=0]
lst2017 = [x for x in primess if primes[(x+1)//2] != 0]

for l, r in lr:
    nr = bisect.bisect_right(lst2017, r)
    nl = bisect.bisect_left(lst2017, l)
    print(nr - nl)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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


q = int(readline())
primelist = makePrimeChecker(10 ** 5 + 2)
check = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    if i % 2 == 1:
        if primelist[i] and primelist[(i + 1) // 2]:
            check[i] += 1
    check[i] += check[i - 1]
lr = [list(map(int, readline().split())) for _ in range(q)]
for l, r in lr:
    print(check[r] - check[l - 1])

Submission status: Accepted

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

is_prime = primes(10**5)
like = [False] * 10**5
for i in range(3, 10**5, 2):
    if is_prime[i] and is_prime[(i+1)//2]:
        like[i] = True

cusum = [0] * 10**5
for i in range(3, 10**5, 2):
    cusum[i] = cusum[i-2] + like[i]

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

    if l == 1:
        print(cusum[r])
    else:
        print(cusum[r] - cusum[l-2])

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter

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

rmax = max(lr, key=itemgetter(1))[1]
primes = list(range(rmax+1))
primes [1] = 0

for i in range(2, int(rmax**0.5)+ 2):
    for j in range(2 * i, rmax+1, i):
        primes[j] = 0
primes = [prime for prime in primes[:] if prime!=0]

lst2017 = [x for x in primes if x != 2 and (x+1)//2 in primes]

for l, r in lr:
    nr = bisect.bisect_right(lst2017, r)
    nl = bisect.bisect_left(lst2017, l)
    print(nr - nl)

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
    
def find_prime(n):
    prime_list = []
    find_list = list(range(2,n+1))
    while True:
        if find_list[0] > n**(1/2):
            prime_list.extend(find_list)
            break
        else:
            head = find_list[0]
            prime_list.append(head)
            find_list.pop(0)
            find_list = [num for num in find_list if num % head != 0]
    return prime_list

find_prime_s = find_prime(50000)
like2017 = []
for i in find_prime(100000)[1:]:
    if (i+1)//2 in find_prime_s:
        like2017.append(i)

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

Submission status: Accepted

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

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')


n_queries = int(input())
queries = []
for _ in range(n_queries):
    l, r = map(int, input().split())
    queries.append([l, r])

MAX_INT = 10 ** 5


def eratos(number):
    is_prime = [1] * (number + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, number + 1):
        if not is_prime[i]:
            continue
        j = i + i
        while j < number + 1:
            is_prime[j] = 0
            j += i
    return is_prime


def like(number):
    is_like = [0] * (number + 1)
    for i in range(number + 1):
        if i % 2 == 0:
            continue
        if is_prime[i] and is_prime[(i + 1) // 2]:
            is_like[i] = 1
    return is_like


is_prime = eratos(MAX_INT)
is_like = like(MAX_INT)

cum_sum = [0] * (MAX_INT + 2)
for i in range(MAX_INT + 1):
    cum_sum[i+1] = cum_sum[i] + is_like[i]

for l, r in queries:
    res = cum_sum[r+1] - cum_sum[l]
    print(res)

Submission status: Accepted

Solution code:
Q = int(input())
Start = []
End = []
for _ in range(Q):
    l, r = map(int, input().split())
    Start.append(l)
    End.append(r)

e = max(End)


def primes(n):
    ass = set([])
    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.add(i)
    return ass


def like_primes(n):
    A = [0] * (e+2)
    for i in range(1, e+2):
        if (i in n) and ((i + 1) // 2 in n):
            A[i] = A[i-1] + 1
        else:
            A[i] = A[i-1]
    return A


A = like_primes(primes(e))
for i in range(Q):
    print(A[End[i]] - A[Start[i]-1])

Submission status: Accepted

Solution code:
import math
def prime(n):
    k = 2
    while k<=math.sqrt(n):
        if n % k == 0:
            # print(k,"の倍数です")
            return False
        k += 1
    return True
l = [0]*(10**5+1)
for i in range(2,10**5+1):
    if prime(i) and prime(int((i+1)/2)):
        l[i] += 1
l[2] = 0
# print(l[:10])
for i in range(10**5):
    l[i+1] = l[i] + l[i+1]

# print(l[:10])
# print(prime(35))    
q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    print(l[b] - l[a-1])

Submission status: Accepted

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

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

qu = [0]
now = 0
for i in range(0,50000):
    if is_prime(2*i+1) and is_prime(i+1):
        now+=1
        qu.append(now)
    else:
        qu.append(now)

for i in range(Q):
    qlis = lis[i]
    minin = int((qlis[0]-1)/2)
    maxin = int((qlis[1]+1)/2)
    print(qu[maxin]-qu[minin])

Submission status: Accepted

Solution code:
q=int(input())
A=[0 for i in range(10**5+23)]
P=[0 for i in range(10**5+23)]
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,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]

for i in eratosu(10**5+6):
    P[i]=1
for i in range(1,len(A)):
    if P[i]==1 and P[(i+1)//2]==1:
        A[i]=A[i-1]+1
    else:
      A[i]=A[i-1]

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

Submission status: Accepted

Solution code:
def sieve(n):
	is_prime = [1] * (n + 1)
	is_prime[0], is_prime[1] = 0, 0
	for i in range(2, n+1):
		if not is_prime[i]:
			continue
		j = i*2
		while j <= n:
			is_prime[j] = 0
			j += i
	return is_prime

def resolve():
	q = int(input())
	qs = [list(map(int, input().split())) for _ in range(q)]
	ps = sieve(10**5)
	seq = [0] * (10**5+1)
	for i in range(len(ps)-1, 1, -1):
		if ps[i] and ps[(i+1)//2]:
			continue
		ps[i] = 0
	for i in range(1, 10**5):
		seq[i+1] = seq[i] + ps[i+1]
	for l, r in qs:
		if l == r:
			print(ps[l])
		else:
			print(seq[r] - seq[l-1])
resolve()

Submission status: Accepted

Solution code:
def isprime(n):
    '''check if integer n is a prime'''

    # make sure n is a positive integer
    n = abs(int(n))

    # 0 and 1 are not primes
    if n < 2:
        return False

    # 2 is the only even prime number
    if n == 2:
        return True

    # all other even numbers are not primes
    if not n & 1:
        return False

    # range starts with 3 and only needs to go up
    # the square root of n for all odd numbers
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False

    return True

def resolve():
	q = int(input())
	qs = [list(map(int, input().split())) for _ in range(q)]
	t = [0]*(10**5+1)
	for i in range(10**5):
		v = 1 if isprime(i+1) and isprime((i+2)/2) else 0
		t[i+1] = t[i] + v
	for l, r in qs:
		if l == r:
			print(1 if isprime(l) and isprime((l+2)/2) else 0)
		else:
			print(t[r] - t[l-1])
resolve()

Submission status: Accepted

Solution code:
import math
N = 100001
pr = [True]*(N+1)
pr[0] = pr[1] = False
for i in range(2,int(math.sqrt(N))) :
    if pr[i]:
        for j in range(i+i,N,i):pr[j] = False

c = [0]*(N+1)

for i in range(3,N,2):
    if pr[i] and pr[(i+1)//2]:
        c[i]+=1
for i in range(3,N):
    c[i]+=c[i-1]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(c[r]-c[l-1])

Submission status: Accepted

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

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

sum_a = [0]*100001
for n in range(1, 100000+1):
  if is_prime(n) and is_prime((n+1)//2):
    prime = 1
  else:
    prime = 0
  sum_a[n] = sum_a[n-1] + prime

for l, r in query:
  print(sum_a[r] - sum_a[l-1])

Submission status: Accepted

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

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

prime = [0]*100001
sum_a = [0]*100001
for n in range(1, 100000+1):
  if is_prime(n) and is_prime((n+1)//2):
    prime[n] = 1
  sum_a[n] = sum_a[n-1] + prime[n]

for l, r in query:
  print(sum_a[r] - sum_a[l-1])

Submission status: Accepted

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

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

prime = []
ans = [0]*100001
sum_a = [0]*100001
for n in range(1, 100000+1):
  if is_prime(n) and is_prime((n+1)//2):
    if n != 2:
      prime.append(n)
      ans[n] = 1
  sum_a[n] = sum_a[n-1] + ans[n]

for l, r in query:
  print(sum_a[r] - sum_a[l-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations
from fractions import gcd
#from math import gcd
from math import ceil, floor
import bisect
sys.setrecursionlimit(10 ** 6)
inf = float("inf")

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

# Sieve of Eratosthenes
def is_prime(n):
    a = [None] * n
    non_prime_set = set()
    prime_set = set()
    a[0] = 0
    a[1] = 0
    for i in range(2, n):
        if i not in non_prime_set:
            prime_set.add(i)
            a[i] = 1
            for j in range(i*i, n, i):
                non_prime_set.add(j)
                a[j] = 0
    return(a)

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

    # 2017-like
    MAX = 101010
    prime_list = is_prime(MAX)
    a = [0] * MAX
    for i in range(1, MAX, 2):
        if (prime_list[i] and prime_list[(i+1)//2]):
            a[i] = 1

    s = [0] * (MAX+1)
    for i in range(MAX):
        s[i+1] = s[i] + a[i]

    for i in range(Q):
        print(s[R[i]+1] - s[L[i]])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
rem = defaultdict(int)

def prime_f(m):
    pf = {}
    for i in range(2, int(m**0.5) + 1):
        while not m % i:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf


cnt = 0
for i in range(3, 100000, 2):
    a = tuple(prime_f(i).values())
    if len(a) == 1 and a[0] == 1:
        b = tuple(prime_f((i+1)//2).values())
        if len(b) == 1 and b[0] == 1:
            cnt += 1
            rem[i] = cnt
        else:
            rem[i] = cnt
    else:
        rem[i] = cnt

for i in range(n):
    a, b = map(int, input().split())
    print(rem[b] - rem[a - 2])

Submission status: Accepted

Solution code:
import bisect

numbers_like_2017 = [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, 10333, 10357, 10453, 10837, 10861, 10957, 11113, 11161, 11317, 11497, 11677, 11701, 12073, 12157, 12241, 12301, 12421, 12433, 12457, 12541, 12553, 12601, 12721, 12757, 12841, 12853, 13093, 13381, 13417, 13681, 13921, 13933, 14437, 14593, 14737, 14821, 15013, 15073, 15121, 15241, 15277, 15361, 15373, 15733, 15901, 16033, 16333, 16381, 16417, 16573, 16633, 16657, 16921, 17041, 17053, 17077, 17257, 17293, 17377, 17881, 18013, 18097, 18133, 18181, 18217, 18253, 18301, 18313, 18397, 18481, 18553, 18637, 18793, 19237, 19441, 19477, 19717, 19801, 19813, 19861, 20353, 20533, 20641, 20857, 21001, 21061, 21193, 
21277, 21313, 21577, 21661, 21673, 21817, 22093, 22501, 22573, 22621, 22993, 23053, 23173, 23557, 23677, 23773, 23917, 24097, 24421, 24481, 24781, 24841, 25033, 25153, 25237, 25561, 25657, 25933, 26017, 26293, 26317, 26437, 26497, 26821, 26833, 26881, 26953, 27073, 27253, 27337, 27361, 27457, 27997, 28057, 28297, 28393, 28813, 28837, 28921, 29101, 29473, 29641, 30181, 30241, 30517, 30553, 30577, 30637, 30661, 30697, 30781, 30853, 31081, 31237, 31321, 31333, 31357, 31477, 31573, 31873, 31981, 32173, 32377, 32497, 32533, 32833, 33037, 33301, 33457, 33493, 33757, 33961, 34057, 34213, 34273, 34381, 34513, 34897, 34981, 35317, 35521, 35677, 35977, 36097, 36241, 
36433, 36457, 36793, 36877, 36901, 36913, 37273, 37321, 37357, 37573, 37717, 37957, 38281, 38461, 38833, 38953, 38977, 39217, 39373, 39397, 39733, 40093, 40177, 40213, 40693, 40813, 41017, 41221, 41281, 41413, 41617, 41893, 42061, 42337, 42373, 42793, 42961, 43117, 43177, 43201, 43321, 43573, 43597, 43633, 43717, 44053, 44101, 44221, 44257, 44293, 44893, 45061, 45337, 45433, 45481, 45553, 45613, 45841, 46021, 46141, 46261, 46861, 46993, 47017, 47161, 47353, 47521, 47533, 47653, 47713, 47737, 47797, 47857, 48121, 48193, 48337, 48673, 48757, 48781, 49033, 49261, 49393, 49417, 49597, 49681, 49957, 50221, 50341, 50377, 50821, 50893, 51157, 51217, 51241, 51481, 
51517, 51637, 52057, 52081, 52237, 52321, 52453, 52501, 52813, 52861, 52957, 53077, 53113, 53281, 53401, 53917, 54121, 54133, 54181, 54217, 54421, 54517, 54541, 54673, 54721, 54973, 55057, 55381, 55501, 55633, 55837, 55921, 55933, 56053, 56101, 56113, 56197, 56401, 56437, 56701, 56773, 56821, 56857, 56893, 57073, 57097, 57193, 57241, 57373, 57457, 57853, 58153, 58417, 58441, 58537, 58573, 58693, 59053, 59197, 59221, 59281, 59341, 59833, 60217, 60337, 60373, 60637, 60733, 60937, 61057, 61153, 61261, 61297, 61561, 61657, 61681, 61717, 61861, 62137, 62473, 62497, 62533, 62653, 62773, 63313, 63397, 63541, 63697, 63781, 63913, 64153, 64237, 64381, 64513, 64717, 
65173, 65293, 65413, 65437, 65497, 65557, 65677, 65881, 66301, 66361, 66601, 66697, 66853, 66973, 67057, 67153, 67273, 67477, 67537, 67741, 67777, 67933, 67993, 68113, 68281, 68521, 68737, 69001, 69073, 69457, 69493, 69697, 69877, 70117, 70177, 70297, 70501, 70621, 70921, 70981, 71233, 71341, 71353, 71593, 71821, 72073, 72481, 72613, 72901, 72937, 73141, 73417, 73477, 73561, 73693, 74077, 74317, 74377, 74713, 75013, 75133, 75181, 75721, 75793, 75913, 76333, 76561, 76597, 76753, 77137, 77641, 78157, 78193, 78277, 78877, 78901, 79333, 79357, 79537, 79657, 79693, 79801, 79873, 80077, 80173, 80221, 80473, 80701, 80713, 80917, 81013, 81181, 81517, 81637, 81853, 
82021, 82153, 82261, 82561, 82981, 83077, 83221, 83233, 83437, 83617, 83701, 83773, 84121, 84313, 84673, 84697, 84793, 84913, 85297, 85333, 85453, 85717, 85933, 86353, 86413, 87181, 87253, 87337, 87421, 87433, 87517, 87553, 87973, 88117, 88177, 88237, 88261, 88513, 88741, 88897, 88993, 89293, 89833, 89917, 90121, 91081, 91381, 91393, 91513, 91957, 92041, 92557, 92761, 92821, 92893, 92941, 93097, 93133, 93493, 93637, 93913, 94033, 94117, 94273, 94321, 94441, 94573, 94777, 94837, 94993, 95257, 95317, 95401, 95581, 95617, 95713, 95737, 96097, 96157, 96181, 96493, 96517, 96973, 97081, 97177, 97501, 97561, 97777, 97813, 98017, 98737, 98953, 99277, 99577, 99661, 
99877]

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
import math
    
def is_prime(x):
    if x < 2: return False
    if x == 2 or x == 3 or x == 5: return True  # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False  # 2,3,5の倍数は合成数
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False
        prime += step
        step = 6 - step
    return True

def main():
    Q = int(readline())
    is_2017 = [True] * (10**5 // 2)
    for i in range(10**5//2):
        if not is_prime(2*i+1):
            is_2017[i] = False
        if not is_prime(i+1):
            is_2017[i] = False

    is_2017[0] = 0
    for i in range(1, 10**5//2):
        is_2017[i] += is_2017[i-1]
    
    for _ in range(Q):
        l, r = map(int, readline().rstrip().split())
        if l == 1:
            print(is_2017[(r-1)//2])
        else:
            print(is_2017[(r-1)//2] - is_2017[(l-1)//2-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def pm_table(n):
    """
    素数テーブル
    nのリストを返却する
    :param n:
    """
    res = [1] * (n + 1)
    res[0] = 0
    res[1] = 0

    for i in range(2, n):
        if i ** 2 > n:
            break

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


N = 10 ** 5
pm = pm_table(N)

a = [0] * (N + 1)
for i in range(1, N + 1, 2):
    if pm[i] == 1 and pm[(i + 1) // 2] == 1:
        a[i] = 1
s = [0] * (N + 2)
for i in range(N + 1):
    s[i + 1] = s[i] + a[i]

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

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
Q = int(input())
LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

@lru_cache(maxsize=None)
def isprime(x):
    if x == 1:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

s = [0] * (10 ** 5 + 1)
for x in range(1, len(s)):
    s[x] = s[x-1]
    if isprime(x) and isprime((x + 1) // 2):
        s[x] += 1

for l, r in LR:
    ans = s[r] - s[l-1]
    print(ans)

Submission status: Accepted

Solution code:
#素数判定
import math
from itertools import accumulate
def sosuu(n):
  if n==1:
    return False
  else:
    for i in range(2,int(math.sqrt(n)+1)):
      if n%i==0:
        return False
    return True

#入力
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=list(map(int,input().split()))
L=min(l)
R=max(r)

#累積和を作る
A=[]
for i in range(L,R+1):
  if i%2==0:
    A.append(0)
  else:
    if sosuu(i) and sosuu(int((i+1)/2)):
      A.append(1)
    else:
      A.append(0)
s=[0]+A
S=list(accumulate(s))
for i in range(q):
    #print(S[r[i]-L+1])
    #print(S[l[i]-L])
    print(S[r[i]-L+1]-S[l[i]-L])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_right


def cal_prime(N):
    prime_list = set()
    ans_list = set()
    for i in range(2, N):
        flag = True
        for j in range(2, int(i**0.5)+1):
            if i % j == 0:
                flag = False
                break
        if flag:
            prime_list.add(i)
            if i > 2 and (i+2) // 2 in prime_list:
                ans_list.add(i)
    return sorted(ans_list)


def main():
    Q = int(input())
    ans_list = cal_prime(10**5)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
def sieve_of_eratosthenes_2017(N):
    numbers = [n & 1 for n in range(N + 1)]
    numbers[1] = 0
    numbers[2] = 1
    like2017 = [0] * (N + 1)
    p = 1
    while True:
        while not numbers[p]:
            p += 2
        if p * p > N:
            for i in range(p, N + 1, 2):
                if numbers[i] & numbers[(i + 1) >> 1]:
                    like2017[i] = 1
            return like2017
        if numbers[(p + 1) >> 1]:
            like2017[p] = 1
        for i in range(p * 2, N + 1, p):
            numbers[i] = 0
        p += 2

like2017 = sieve_of_eratosthenes_2017(10 ** 5)
like2017_sum = list(accumulate(like2017))
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(like2017_sum[r] - like2017_sum[l] + like2017[l])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect
def sieve_of_eratosthenes_2017(N):
    numbers = [n & 1 for n in range(N + 1)]
    numbers[1] = 0
    numbers[2] = 1
    like2017 = []
    p = 1
    while True:
        while not numbers[p]:
            p += 2
        if p * p > N:
            for i in range(p, N + 1, 2):
                if numbers[i] & numbers[(i + 1) >> 1]:
                    like2017.append(i)
            return like2017
        if numbers[(p + 1) >> 1]:
            like2017.append(p)
        for i in range(p * 2, N + 1, p):
            numbers[i] = 0
        p += 2

like2017 = sieve_of_eratosthenes_2017(10 ** 5)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    lindex = bisect_left(like2017, l)
    rindex = bisect(like2017, r)
    print(rindex - lindex)

Submission status: Accepted

Solution code:
from itertools import accumulate
def sieve_of_eratosthenes_2017(N):
    numbers = [n & 1 for n in range(N + 1)]
    numbers[1] = 0
    numbers[2] = 1
    like2017 = [0] * (N + 1)
    p = 1
    while True:
        while not numbers[p]:
            p += 2
        if p * p > N:
            for i in range(p, N + 1, 2):
                if numbers[i] & numbers[(i + 1) >> 1]:
                    like2017[i] = 1
            return like2017
        if numbers[(p + 1) >> 1]:
            like2017[p] = 1
        for i in range(p * 2, N + 1, p):
            numbers[i] = 0
        p += 2

like2017 = sieve_of_eratosthenes_2017(10 ** 5)
like2017_sum = list(accumulate(like2017))
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(like2017_sum[r] - like2017_sum[l] + like2017[l])

Submission status: Accepted

Solution code:
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
d, ans = [0]*(10**5+1), [0]*(10**5+1)
for i in primes(10**5): d[i] += 1
for i in range(2, 10**5+1):
    ans[i] += ans[i-1]
    if i%2==1 and d[i] and d[(i+1)//2]: ans[i] += 1
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])