1.2.1. 素数列挙

Code: composite_and_prime.py
Test: test_composite_and_prime.py

素数とは

自分自身と1以外の約数を持たない自然数を素数という。

実装

概要

エラトステネスの篩 (Wikipedia)

エラトステネスの篩を用いて \(n\) 以下の素数を列挙する。
小さい数から順に数表を調べ、自身とその倍数に訪問済みの印をつけていく。
\(a\) が合成数ならば、\(a\) の倍数を走査しようとするとき既に訪問済みとなっている。
primes_table

全ての倍数を走査し終えると、素数判定に使える数表が得られる。

is_prime_table

実装のポイント

合成数の倍数はそれより小さな素数の倍数で既に走査しているため、素数だけ走査すればよい。

計算量

  • sieve(n) \(\mathcal{O}(n \log{\log{n}})\)

コード

[1]:

from __future__ import annotations


def sieve(n: int) -> list[int]:
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for a in range(2, n+1):
        if is_prime[a]:
            primes.append(a)
            for i in range(a*a, n+1, a):
                is_prime[i] = False
    return primes

使用例

[2]:

primes = sieve(100)
print(*primes[:10])

2 3 5 7 11 13 17 19 23 29