Telling If a Number is Prime

素数を扱う簡単なアルゴリズムはO(√n)で行えます。以下の何れのアルゴリズムもO(√n)で行うことができます。

プログラミングコンテストチャレンジブックでは二つの式を使って簡潔に説明をしています(p. 111)。

例えばnの素因数分解を考えるときは2〜√nまでの整数を考えればよいということなのですが、どうも頭がこんがらがってしまうことがあります。そのため図にして少し考えてみました。

図の右端がnです。私達は今、2について考えています。2がnの約数であるとすると、n/2もnの約数です。

この時点でn/2からnまでの間の黒い部分にはもう約数が存在しないことが分かります。2を考えるだけで扱う量がすでに半分になってしまったのです。

次に3を考えます。先ほどと同様に、n/3からn/2までにももう約数が存在しないことが分かってしまいました。

これを繰り返します。

さて、これらの図はnを41として作成しています。√41は大体6.4です。5になるとほとんどの数値の判定が終わってしまうことになります。

最後に6をチェックして終了です。

nが素数かどうかは、2〜√nまでに割り切れる数があるかないかを調べることで判定できます。

nの素因数分解を行うときは2〜√nまでの整数がnを割り切るかどうかを調べます。その整数がnを割り切る場合、nの素因数であると判断できます。その素因数でnを割り、続けます。

2〜√nまでの整数で試し、それでもnが1にならない場合、そのnも素数です。このnは元々のnかもしれません。そうではない場合、n/2より小さい値となります。

以下のような素数の集合からなる数列が用意出来ていればそれを用いるのもよいですが、大抵は2〜√nまでの全ての整数を用いても十分のようです。

以下はここまでを元に素数判定を実装したものになります。ほとんど工夫をする余地がなく、インデント以外はプログラミングコンテストチャレンジブックと変わらないものとなっています。

bool is_prime(int n)
{
  for (int i = 2; i * i <= n; i ++)
    if (n % i == 0)
      return false;

  return n != 1;
}

実装時に特に気を付けなければならないのは最後の判定でしょう。これを以下のようにしてしまうと、nが1であるときに素数である、と誤判定してしまいます。

          :
  return true;
}