Submission #2123716

---

Source Code Expand

import math

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

primes = list(range(M+1))
primes[0] = 0
primes[1] = 0
cut_root = math.sqrt(M+1)
for prime in primes:
	if prime > cut_root:
		break
	if prime == 0:
		continue
	for non_prime in range(2 * prime, M, prime):
		primes[non_prime] = 0
similar_2017 = [0 for _ in range(M+1)]
similar_2017[3] = 1
for i in range(5, M+1, 4):
	if primes[i] != 0:
		if primes[(i+1)//2] != 0:
			similar_2017[i] = 1
similar_sum = [0 for _ in range(M+1)]
for i in range(1,M+1):
	if similar_2017[i] == 1:
		similar_sum[i] = similar_sum[i-1] + 1
	else:
		similar_sum[i] = similar_sum[i-1]

for l, r in li:
	print(similar_sum[r] - similar_sum[l-1])

Submission Info

Judge Result