エラトステネスの篩

$N$ 以下の各整数の最小素因数（smallest prime factor）を篩で求めておきます。素数の一覧だけでなく、 $N$ 以下の整数を何度も素因数分解するときに便利です。

• Sieve(N): 前計算。 $O(N \log \log N)$
• primes: $N$ 以下の素数の昇順リスト
• spf[x]: $x$ の最小素因数（ $x \ge 2$）
• is_prime(x): $x$ が素数か（ $0 \le x \le N$）。 $O(1)$
• factorize(x): [(素因数, 指数), ...] を素因数の昇順で返す（ $1 \le x \le N$）。 $O(\log x)$
• divisors(x): 約数を昇順で返す（ $1 \le x \le N$）。 $O(d(x) \log d(x))$

区間篩

$R$ が大きくても区間の幅 $R - L$ が小さい（ $10^6$ 程度）ときに、 $L$ 以上 $R$ 未満の素数を求めます。 $\sqrt{R}$ 以下の素数で区間 $[L, R)$ だけを篩います。

• segment_sieve(L, R): $L \le x < R$ を満たす素数の昇順リストを返す（ $0 \le L$）。 $O(\sqrt{R} \log \log R + (R - L) \log \log R)$

コード

from math import isqrt


class Sieve:
    def __init__(self, n):
        spf = list(range(n + 1))
        for i in range(2, isqrt(n) + 1):
            if spf[i] == i:
                for j in range(i * i, n + 1, i):
                    if spf[j] == j:
                        spf[j] = i
        self.spf = spf
        self.primes = [i for i in range(2, n + 1) if spf[i] == i]

    def is_prime(self, x):
        return x >= 2 and self.spf[x] == x

    def factorize(self, x):
        # [(素因数, 指数), ...]
        res = []
        while x > 1:
            p = self.spf[x]
            e = 0
            while x % p == 0:
                x //= p
                e += 1
            res.append((p, e))
        return res

    def divisors(self, x):
        res = [1]
        for p, e in self.factorize(x):
            m = len(res)
            q = 1
            for _ in range(e):
                q *= p
                for i in range(m):
                    res.append(res[i] * q)
        res.sort()
        return res


def segment_sieve(l, r):
    # l <= x < r の素数のリスト
    if r <= l:
        return []
    k = isqrt(r - 1)
    small = bytearray([1]) * (k + 1)
    is_p = bytearray([1]) * (r - l)
    for x in range(l, min(r, 2)):
        is_p[x - l] = 0
    for i in range(2, k + 1):
        if small[i]:
            small[i * i::i] = bytearray(len(range(i * i, k + 1, i)))
            start = max(i * i, (l + i - 1) // i * i) - l
            is_p[start::i] = bytearray(len(range(start, r - l, i)))
    return [l + i for i in range(r - l) if is_p[i]]