イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

68. 「エラトステネスの篩」の計算量はとりあえず O(N log N) で抑えられる

プログラミング 数学 アルゴリズム

「エラトステネスの篩」は素数列挙に使われる効率的なアルゴリズムです。

  1. 「2」から「対象とする最大値」までを「素数候補」とする
  2. 残っている数のうち最小値を「素数」と判定して「素数候補」から除外する
  3. 2. で素数と判定した倍数を、全て「素数候補」から除外する
  4. 「素数候補」が空なら終了、空でないなら 2. に移動

 

このアルゴリズムの計算量ですが、「対象とする最大値」を N として O(N \log \log N) になるらしいです。ただ、こちらの証明は難しいらしく、もっと簡単に O(N \log N) で抑えられることを示せます。

エラトステネスの篩で「素数候補からの除外」操作を行う対象は、素数と判定した数を p として高々 \displaystyle \frac{N}{p} 個あります。つまり、エラトステネスの篩で素数候補である数を見る回数を F(N) とすると、以下の式が成り立ちます。

 

 \begin{eqnarray} \displaystyle F(N) & \le & \frac{N}{2} + \frac{N}{3} + \frac{N}{5} + \frac{N}{7} + \frac{N}{11} + \cdots + \frac{N}{N} \\\ \displaystyle & \le & N \left(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} +  \cdots + \frac{1}{N} \right) \end{eqnarray}

 

ここで、括弧の中身は調和級数 \displaystyle \sum_{k=1}^{N} \frac{1}{k} です。調和級数は O(\log N) です。

ibako-piyo.hatenablog.com

よって、 F(N) は O(N \log N) で抑えられることが分かりました。