エラトステネスの篩

概要

$n$ 以下の素数を全て高速で列挙するアルゴリズム。
通常の方法でやれば計算回数が $O(n\sqrt{n})$ になるところ、$O(n\log\log n)$ で済む。

アルゴリズム内容

$n=20$ の場合、以下のようにする。
灰色の部分が消した数である。

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

具体的なコードは、

• $n+1$ 要素の bool 型の vector を用意し、true で初期化
• $0$ と $1$ は素数でないので false にする
• $2$ 以上 $\sqrt{n}$ 以下の全ての素数 $i$ について、$i^2$ 以上 $n$ 以下の $i$ の倍数を全部消すループをする

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

C++での実際の参考コードは以下。
これは $n$ 以下の素数を求めるコードである。

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

応用

同様の方法で、$n$ 以下の全ての数の最小素因数を求めることができる。
上書きしないことと、素数のところを埋めるために $n$ まできっちり回す必要があることに注意。

C++での実際の参考コードは以下。

vector<int> s_primes;
void make_s_primes (int n) {
  assert(n>=0);
  s_primes.assign(n+1,-1);
  bool flag = true;
  for (int i=2; i<=n; i++) {
    if (s_primes[i]!=-1) continue;
    s_primes[i] = i;
    if (!flag) continue;
    for (int j=i*i; j<=n; j+=i) {
      if (s_primes[j]==-1) s_primes[j] = i;
    }
    if (i*i>n) flag = false;
  }
}

注意点

$\sqrt{n}$ 以下という判定は整数型で行うこと

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

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

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

関連知識

素数判定

通常の素数判定を用いて $n$ 以下の数 $m$ 個を判定するのに $O(m\sqrt{n})$ かかる。
つまり、$m$ が $\sqrt{n}\log\log n$ より小さいなら、通常の方法の方が速い。

区間篩

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

素因数分解

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