累積和の問題
結構昔の問題です。今更ながら、累積和の勉強の為に解いてみました。
##解法
「エラトステネスの篩 (ふるい)」という手法を使うと、素数テーブルを高速に作成することができます。
そのテーブルとは、配列のインデックス $i$ が素数だった場合、その要素が True となる配列のことです。
この問題では作成した素数テーブルを用いて、「2017に似た数」かどうかを判定し、累積和 という手法を用いることでより高速に「2017に似た数」が何個あるか数えられます。
##コード
like2017.py
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
N = 10 ** 5
prime = [True] * (N + 1)
prime[0] = prime[1] = False
# 素数テーブルの作成 (エラトステネスのふるい)
for i in range(2, N + 1):
if prime[i]:
for j in range(i * i, N + 1, i):
prime[j] = 0
# 2017 like number の累積和テーブルの作成
like2017 = [0] * (N + 1)
for n in range(1, N + 1):
if prime[n] == 0: # n がそもそも素数でなかったから前の値で更新
like2017[n] = like2017[n - 1]
continue
query = (n + 1) // 2 # n は素数なので奇数であり、n + 1 は必ず 2 で割り切れる数となっている
if prime[query] == 1: # (n + 1) // 2 も素数だから、1 を足した値で更新
like2017[n] = like2017[n - 1] + 1
else: # n は素数だったけど、(n + 1) // 2 が素数でなかったから前の値で更新
like2017[n] = like2017[n - 1]
for l, r in lr:
print(like2017[r] - like2017[l - 1])
##参考