Day 093-Q5 — 区間篩（Segmented Sieve）

問題

2つの整数 $L, R$（$L \le R$）が与えられる。区間 $[L, R]$ に含まれる素数の個数を求めよ。

入出力例

10 20

4

区間$[10,20]$の素数は$11,13,17,19$の4個。

999999999989 1000000000000

1

概念図

ヒント

limit = int(math.isqrt(R)) + 1
# limitまでの通常の篩でbase_primesを得る
size = R - L + 1
is_prime_range = [True] * size
for p in base_primes:
    start = max(p * p, ((L + p - 1) // p) * p)
    for multiple in range(start, R + 1, p):
        is_prime_range[multiple - L] = False

模範解答

import sys
import math


def main():
    data = sys.stdin.buffer.read().split()
    L = int(data[0])
    R = int(data[1])

    if R < 2:
        print(0)
        return

    limit = int(math.isqrt(R)) + 1

    is_prime_small = [True] * (limit + 1)
    is_prime_small[0] = False
    if limit >= 1:
        is_prime_small[1] = False
    for i in range(2, int(math.isqrt(limit)) + 1):
        if is_prime_small[i]:
            for j in range(i * i, limit + 1, i):
                is_prime_small[j] = False
    base_primes = [i for i, v in enumerate(is_prime_small) if v]

    size = R - L + 1
    is_prime_range = [True] * size
    if L == 0:
        if size > 0:
            is_prime_range[0] = False
        if size > 1:
            is_prime_range[1] = False
    elif L == 1:
        is_prime_range[0] = False

    for p in base_primes:
        start = max(p * p, ((L + p - 1) // p) * p)
        for multiple in range(start, R + 1, p):
            is_prime_range[multiple - L] = False

    print(sum(is_prime_range))


main()

計算量: $\sqrt{R}$までの篩が$O(\sqrt{R}\log\log\sqrt{R})$、区間篩が$O((R-L)\log\log R)$程度。

Step-by-Step 解説

Step 1: base_primes（$\sqrt{R}$以下の素数）を求める

合成数$x\le R$は必ず$\sqrt{x}\le\sqrt{R}$以下の素因数を持つため、その範囲の素数さえ分かれば区間内の合成数を全て篩い落とせる。

Step 2: 区間配列の準備とオフセット管理

is_prime_range[i]が実数L+iに対応するように配列を作る。

Step 3: 各素数$p$について区間内の倍数を篩い落とす

start = max(p*p, ceil(L/p)*p)として不要な走査を避ける。

Step 4: $L\le1$の特別処理と集計

1は素数ではないため区間に含まれる場合は明示的に除外し、最後にTrueの個数を数える。

よくあるミス

次のステップ

• 発展: 区間内の素因数分解（各数の最小素因数を区間篩で同時記録）
• 発展: Lucy_Hedgehogの篩（Day078 Q5）との比較
• 次回予告: 未定（Master Levelローテーション継続）

自己評価