素数列挙(Sieve of Eratosthenes)
説明
エラトステネスの篩による素数列挙アルゴリズム。指定された自然数以下の全ての素数を発見するための単純なアルゴリズム。具体的には, まず $2$ の倍数を除外する。次に $3$ の倍数を除外する。 $4$ は除外されているので $5$ の倍数を除外する。 $6$ は除外されているので $7$ を除外する。... というふうに, 素数の倍数を貪欲に除外していく。
計算量
$O(N \log \log N)$
実装例
エラトステネスの篩による素数列挙アルゴリズム。指定された自然数以下の全ての素数を発見するための単純なアルゴリズム。具体的には, まず $2$ の倍数を除外する。次に $3$ の倍数を除外する。 $4$ は除外されているので $5$ の倍数を除外する。 $6$ は除外されているので $7$ を除外する。... というふうに, 素数の倍数を貪欲に除外していく。
$O(N \log \log N)$