競技プログラミングお役立ちライブラリ① ~エラトステネスの篩~

前書き

初投稿です。

AtCoderの問題を解いていて__「こんなことをいちいち1から書いてられるかー！！」__という場面がちらほら出てきたのでライブラリを作成することにしました。覚書の意味もかねてライブラリのソースコードを紹介します。

目的はライブラリ紹介なので、アルゴリズムの解説は最低限にとどめる予定です。こここうしたほうがいいよみたいなのがあればおしえていただけるとありがたいです。

概要

__エラトステネスの篩__は、$N$以下の全ての非負整数に対して素数判定を行ってくれるアルゴリズムです。何をやっているかはWikipediaのgifがわかりやすいです。

計算量は__$O(N)$より少し大きいくらい__です。(正確には($N$以下の素数の逆数の和)*_$O(N)$_で、素数の逆数は発散するのですが、発散のスピードがこんな感じなので競プロで使う範囲内なら実質$O(N)$として問題なさそうです)

使用例

• ABC 084 D - 2017-like Number 10^5以下の素数を列挙するのに使用します。
• ABC 052 C - Factors of Factorial
  $N!$の素因数が全て$N$以下であることを利用します。

実装

# include <iostream>
# include <vector>
# include <cmath>
using namespace std;

const int N = pow(10,5);

vector<bool> isp(N+1, true);

void sieve() {
  isp[0] = false;
  isp[1] = false;
  for (int i=2; pow(i,2)<=N; i++) {
    if (isp[i]) for(int j=2; i*j<=N; j++) isp[i*j] = false;
  }
}

int main() {
  // N以下の整数に対して素数判定をしてくれます。
  // nが素数ならば isp(n)=true、そうでなければ isp(n)=false
  sieve();
  // ex. 51から80までの素数を出力
  for (int i=51; i<=80; i++) if (isp[i]) cout << i << endl;
  return 0;
}

実行結果

53
59
61
67
71
73
79