Eratosthenesの篩
Abstract
Eratosthenesの篩 (sieve of Eratosthenes) は, 与えられた正整数$ n以下の素数をすべて列挙する$ O(n \log \log n)timeのアルゴリズム.
Explanation
TODO きちんと書く.
Theorem
正整数$ kに対し, $ kが合成数ならば, $ kは$ \sqrt{k}以下の素数$ pを素因数に持つ.
Proof
合成数$ kが $ m個の異なる素数$ p_i ~ (i = 1, \dots, m)を用いて
$ k = \prod_{i = 1}^{m} p_i^{e_i} \quad (e_i \ge 1)
と素因数分解されるとする (ただし, $ kは合成数なので, $ m = 1かつ$ e_1 = 1となることはない).
素因数$ p_iたちがすべて$ \sqrt{k}より大きいと仮定すると, $ E = \sum_{i = 1}^{m} e_iとして
$ k = \prod_{i = 1}^{m} p_i^{e_i} > \prod_{i = 1}^{m} \sqrt{k}^{e_i} = k^{E / 2}
となるが, $ m = 1かつ$ e_1 = 1ではないので$ E \ge 2. よって, 右辺は$ k以上の数となり矛盾. $ \blacksquare
Algorithm (Eratosthenesの篩)
Input:
正整数$ n
Output:
素数表$ T
1. $ T \gets \varnothing とする. $ n < 2なら, $ Tを出力して終了.
2. Bool値の配列$ \mathrm{prime}[0...n] をすべて$ \mathtt{True} で初期化した後, $ \mathrm{prime}[0] \gets \mathtt{False} , $ \mathrm{prime}[1] \gets \mathtt{False} とする.
3. $ p \gets 2と初期化し, $ p \le \sqrt{n}となるまで次の操作を繰り返す:
3-1 $ \mathrm{prime}[p] = \mathtt{True} であれば, 次を行う:Step 3-1で$ iを, $ 2p以上でなく, $ p^2以上の$ pの倍数をチェックするようにしているのは, $ 2p, 3p, \dots, (p-1)pをすでにチェックしているから.
$ p^2 以上$ n 以下のすべての$ p の倍数$ q について$ \mathrm{prime}[q] \gets \mathtt{False} とする.
3-2 $ p \gets p+1と更新する.
4.$ T \gets \{ p \mid \mathrm{prime}[p] = \mathtt{True} \} とし, $ Tを出力する.
Eratosthenesの篩の計算量は次のとおり.
Theorem (Eratosthenesの篩の計算量)
Eratosthenesの篩の計算量は, $ O(n \log \log n)time.
Proof
略. $ \blacksquare cf.) Mertensの定理, Meissel–Mertens定数
Implementation
Input
正整数 n
Output
素数のリスト
Time complexity
$ O(n \log \log n)time.
code:python
def sieve_of_eratosthenes(n):
# O(n loglog n) implementation.
# returns prime numbers <= n.
if n < 2: return []
p = 2
while p * p <= n:
# don't need to check 2p ~ (p-1)p (they've already been checked).
for i in range(p * p, n + 1, p): primei = False p += 1
return [i for i in range(n + 1) if primei] Verification
色々.
References
R.Crandall & C.Pomerance, 『素数全書 —計算からのアプローチ—』, 朝倉書店, 2010.