Algorithms/Mathematics/Prime Number/Primality Test

Primality Test

素数判定

Outline

素数判定は、ある自然数kが素数であるかどうかを判定するアルゴリズムである.
いくつかの例外処理を加えることで効率はよくなるが、
ICPCなどで使う場合には以下の三つの判定さえすれば上手くいく.

1. &mimetex(k=2);なら素数.そうでなければ2へ.
2. &mimetex(k=1);か、もしくは&mimetex(k \equiv 0 \pmod{2});なら素数ではない.
   そうでなければ3へ.
3. &mimetex(3 \leq i \leq \lfloor \sqrt{k} \rfloor);となるiのうち、&mimetex(i \equiv 1 \pmod{2});であるiでkが割り切れれば素数ではない.
   そうでなければkは素数.

3番目の条件のうち、&mimetex(\lfloor \sqrt{k} \rfloor);まで調べればよいことに気付くには
少し考える必要がある.
&mimetex(k = a \times b (1 \leq a \leq b));となるa,bを考える.
&mimetex(k \equiv 0 \pmod{a});なら、
&mimetex(k \equiv 0 \pmod{b});となることは自明であるから、
aで割った後にbで割り切れるか調べる必要はない.
つまり、&mimetex(1 \leq a \leq b);の条件を満たすような最大のaまで
調べればよいことが分かる.
上の条件でaが最大になるのは、&mimetex(a = b);のときであるから、
&mimetex(a \times a = k);となり、
&mimetex(a = \pm \sqrt{k});となる.
aは自然数であるから、&mimetex(a = \lfloor \sqrt{k} \rfloor);となり、
&mimetex(\lfloor \sqrt{k} \rfloor);まで調べれば良いことが分かる.

素数判定のアルゴリズムは他にもFermat Test?や
Rabin-Miller Strong Pseudoprime Test?があるが、
ICPCでは以下のプログラムで十分である.
しかし他のアルゴリズムも趣味としては非常に興味深いので、
勉強する価値はあるだろう.

Program

自然数kが素数であればtrue、素数でなければfalseを返す関数.

bool is_prime(int k) {
  if(k == 2) {
    return true;
  } else if(k == 1 || (k % 2) == 0) {
    return false;
  } else {
    for(int i = 3 ; i <= (int)sqrt((double)k) ; i += 2) {
      if(k % i == 0) {
        return false;
      }
    }
  }

  return true;
}