素数判定

整数 $x$ が素数であるかどうかを判定する素朴なアルゴリズムは次のようになります。

isPrime( x )
    if x <= 1
        return false

    for i = 2 to x-1
        if x % i == 0
            return false

    return true

このアルゴリズムは、与えられた整数 $x$ が 2 から$x − 1$ までの数で割り切れるかどうかを順番に調べるので、ひとつのデータに対して $O(x)$、全体としては $x_i (i = 1, 2, ..n)$ の合計に比例する計算量がかかり、制限時間内に答えを出力することはできません。そこで、高速化する方法を考えてみましょう。

まず、2 以外の偶数は素数ではないことを利用すれば計算量は半減、さらに $x$ の半分まで調べれば十分と分かればさらに半減させることができます。しかしこれらの工夫を考慮しても $O(x)$ のアルゴリズムに変わりはありません。

素数判定では、「合成数 $x$ は $p \leq \sqrt{x}$ を満たす素因子 $p$をもつ」という性質を利用することができます。ここで、素数ではない数を合成数と言います。例えば、31 が素数かどうかの判定は、31 を 2 から 6 までの数で割ってみれば十分ということになります。もし 7 から30までの数で 31 を割り切れる数が存在するのであれば、すでに調べた 2 から 6 までの数に 31 を割り切れる数が必ず存在するので、6 を超えた数字を調べることは無駄になります。

これを利用すると、2 から $x − 1$ までではなく、2 から $\sqrt{x}$ までについて割り切れるかどうかを調べれば十分なので、$O(\sqrt{x})$ のアルゴリズムに改良することができます。これは、例えば $x$ が 1,000,000 とすると$\sqrt{x}$ = 1,000 となり、素朴なアルゴリズムの半減どころか 1,000 倍速くなります。

この素数判定のアルゴリズムは次のように実装することができます。

isprime(x)
  if x == 2
    return true

  if x < 2 または x が偶数
    return false

  i = 3
  while i <= x の平方根
    if x が i で割り切れる
      return false
    i = i + 2

 return true

Reference

 

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ)

AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。