内容別リスト/数学系/エラトステネスの篩 - 競技プログラミング用 知識集積所

---

雑な説明

n未満の素数を全て高速で列挙するアルゴリズム。
通常の方法でやれば計算回数がO(n√n)になるところ、O(n*loglogn)で済む。

レベル

ABCのD問題以降。

アルゴリズム内容

n=20の場合、以下のようにする。

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	0と1は素数でないので消しておく
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	2*2=4以上の2の倍数を消す
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	3*3=9以上の3の倍数を消す
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	4は合成数なので何もしない
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	5は5*5が20を超えるので終了する

残っているものが20以下の全素数である。

具体的なコードは、

• n要素のbool型のvector（未作成）を用意し、trueで初期化。
• 0と1は素数でないのでfalseにする。
• 2以上√n未満の全ての素数iについて、i*i以上n未満のiの倍数を全部消すループをする。

を書けばいい。
trueのまま残っているものが素数。

C++での実際の参考コードは以下。
これはn未満の素数を求めるコードである。
n以下が必要な場合はn+1を渡すこと。

vector<bool> eratosthenes (int n) {
  vector<bool> flags(n,true);
  flags.at(0) = false;
  flags.at(1) = false;
  for (int i=2; i*i<n; i++) {
    if (!flags.at(i)) continue;
    for (int j=i*i; j<n; j+=i) {
      flags.at(j)= false;
    }
  }
  return flags;
}

応用

同様の方法で、n未満の全ての数の最小素因数を求めることができる。
上書きしないことと、素数のところを埋めるためにn-1まできっちり回す必要があることに注意。
C++での実際の参考コードは以下。

vector<int> smallest_primes (int n) {
  vector<int> primes(n,-1);
  bool flag = true;
  for (int i=2; i<n; i++) {
    if (primes.at(i)!=-1) continue;
    primes.at(i) = i;
    if (!flag) continue;
    for (long long j=i*i; j<n; j+=i) {
      if (primes.at(j)==-1) primes.at(j) = i;
    }
    if (1LL*i*i>=n) flag = false;
  }
  return primes;
}

注意点

√n未満という判定は整数型で行うこと。

sqrt()の計算は重いし、double型の判定は信用ならない。
i*i<nの形で判定すること。

false化ループは素数のときだけ回すこと。

iが合成数のときは忘れずスキップすること。
合成数の場合もループすると、答えは出るが無駄が多くO(n*logn)になってしまう。

関連アルゴリズム

素数判定

通常の素数判定を用いてn以下の数m個の判定するのにO(m√n）かかる。
つまり、mが√n*loglognより小さいなら、通常の方法の方が速い。

区間篩（未作成）

a以上b以下の素数を全て高速で列挙する。
O(b*loglogb)でも十分なら普通にエラトステネスの篩をすればいいが、bが10^12くらいでb-aがそんなに大きくない場合だと区間篩をしなければ間に合わない。

素因数分解

どんな素因数が含まれているかまで調べるやつ。