素数かどうかを判定するアルゴリズム

2020年2月29日数学素数,エラトステネスの篩,素数判定

素数とは 「1 より大きい自然数で、正の約数が 1 と自分自身のみであるような数」です。

ある数 \(n\) が素数かどうかを判定するためには、単純に考えると \(O(n)\) の計算量になりますが、後述する通り実は \(O(\sqrt{n})\) で計算をすることができます。

また、\(O(n \log \log n)\) の前処理を行うと、クエリ \(O(1)\) で素数かどうかを判定することもできます。

アルゴリズム

単純なアルゴリズム（前処理なし）：

  1. \(2\) から \(n-1\) まで以下を繰り返す
    • \(n\) を割った余りが 0 で無いことを確かめる（\(n\) の約数でないことを確かめる）。約数なら\(n\) は素数ではない

効率的なアルゴリズム（前処理なし）：

  1. \(2\) から \(\lfloor \sqrt{n} \rfloor\) まで以下を繰り返す
    • \(n\) を割った余りが 0 で無いことを確かめる（\(n\) の約数でないことを確かめる）。約数なら\(n\) は素数ではない

※ 先程の単純なアルゴリズムは無駄な計算をしています。\(n\) が素数でない場合（約数を持つ場合）、約数として\(2\) から \(\lfloor \sqrt{n} \rfloor\) までの数を少なくとも１つ持っているはずです。逆に言えば、それが存在しなければ素数です。

エラトステネスの篩（前処理あり）：

  • 前処理
    1. 2 から N までのリスト {2,3,4,…,N} を用意しておく
    2. まず、\(p = 2\) としてこれを素数とし、以下を繰り返す。
      1. \(p\) をマークする
      2. \(p^2\) からはじめて \(p\) ずつ増やしながら、リストに同じ数があれば削除する
      3. リスト中のマークされてない数のうち、最小のものを \(p\) としてもう一度ループする。無ければ終了する
    3. 最後に残ったものが素数
  • クエリ
    1. 前処理でできたリストの中に \(n\) が存在するか判定する

※ \(N\) 以下の素数を全て見つけ出す方法として、以上のようなエラトステネスの篩(ふるい)が良く知られています。

計算量

  • 単純なアルゴリズム
    • 前処理：なし
    • クエリ：\(O(n)\)
  • 効率的なアルゴリズム
    • 前処理：なし
    • クエリ：\(O(\sqrt{n})\)
  • エラトステネスの篩
    • 前処理：\(O(N\log\log N)\)
    • クエリ：\(O(1)\)

単純なアルゴリズムでは、\(2\) から \(n-1\) まで \(n\) の約数かどうかを確かめるので、 \(O(n)\) の計算量になります。

効率的なアルゴリズムでは、\(2\) から \(\lfloor \sqrt{n} \rfloor\) まで \(n\) の約数かどうかを確かめるので、 \(O(\sqrt{n})\) の計算量になります。

エラトステネスの篩のアルゴリズムの解析は難しいです。
\(p=2 \) で消去されるものは約 \(\frac{n}{2}\) 個、\(p=3\) で消去されるものは約 \(\frac{n}{3}\) 個、というようになるので、全体での計算回数は \(p\) を素数として以下のようになります。

$$\sum_{p <\sqrt{n}}\frac{n}{p}=\frac{n}{2}+\frac{n}{3}+\frac{n}{5}+\dots$$

これの計算量を求めるのは大変なので省略しますが、\(O(n\log\log n)\) 程度であることが知られています。（気になる方は、How is the time complexity of Sieve of Eratosthenes is n*log(log(n))? などを参考にしてください。）
一度 \(N\) までの素数を全て求めてしまえば、ある数が素数かどうかは \(O(1)\) で判定が可能です。

C++での実装例

単純なアルゴリズム

/*  is_prime(n)
    入力：整数 n
    出力：nが素数かの真偽値
    計算量：O(n)
*/
bool is_prime(long long n) {  // is n prime or not
    for (long long i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

効率的なアルゴリズム

/*  is_prime(n)
    入力：整数 n
    出力：nが素数かの真偽値
    計算量：O(√n)
*/
bool is_prime(long long n) {  // is n prime or not
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

エラトステネスの篩

/*  make_is_prime(N)
    入力：整数 N
    出力：N までの数字が素数か判定したベクトル（i番目がtrueならiは素数）
    計算量：O(nloglogn)
*/
vector<bool> make_is_prime(int N) {
    vector<bool> prime(N + 1, true);
    if (n >= 0) prime[0] = false;
    if (n >= 1) prime[1] = false;
    for (int i = 2; i * i <= N; i++) {
        if (!prime[i]) continue;
        for (int j = i * i; j <= N; j += i) {
            prime[j] = false;
        }
    }
    return prime;
}

エラトステネスの篩の気持ち

以下のようにリストから数字が消去されて、素数が残っていきます。

  • はじめ
    • 2, 3, 4, 5, 6, 7, 8, …, n
  • \(p=2\) として消去
    • 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, …
  • \(p=3\) として消去
    • 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, …
  • \(p=5\) として消去
    • 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, …
  • \(p=7\) として消去
    • 2, 3, 5, 7, 11, 13, 19, 23, 29, 31, 37, 41, 43, 47, 53, …
  • …

練習問題

数学素数,エラトステネスの篩,素数判定