素数判定

概要

与えられた数が素数かどうか判定するアルゴリズム。
試し割り法。

アルゴリズム内容

素数とは、正の約数が $1$ と自分自身しかないような $2$ 以上の整数のこと。
つまり、$n$ が素数かどうか判定するには、$2$ から $n-1$ までどれでも割り切れないことを確認すればよい。
だが、この方法、実は少し工夫ができる。

例えば $299$ が素数かどうか判定する場合。
$299$ は $23$ で割り切れるのだが、実は $299/23=13$ である。
ということは、$13$ を見つけることができるなら $23$ を試す必要がない。
よって、平方して $299$ を超えてしまう $18$ 以上を調べなくてもかまわない。
つまり、$2$ から $298$ までではなく、$2$ から $17$ まで割り切れなければ素数と判断してしまってよい。

これにより、$O(n)$ ではなく $O(\sqrt{n})$ で素数かどうかを判定できる。
もちろん、B問題のように計算量を気にしなくてもいい場合は、$n-1$ まで割ってみてもいい。

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

bool is_prime (long long n) {
  if (n<2) return false;
  if (n%2==0&&n>2) return false;
  for (long long i=3; i*i<=n; i+=2) {
    if (n%i==0) return false;
  }
  return true;
}

注意点

多数の判定には不向き。

この方法は、$1$ つめの判定結果が $2$ つめの判定に何も役立たない。
そのため、判定したい個数が多いとそれに比例して時間がかかる。
その場合は「エラトステネスの篩」の記事参照。（D問題レベル）

また、合わせ技で「$\sqrt{n}$ 以下の素数をエラトステネスの篩で探して試し割りをする」ということもできる。
ほどほどの個数だとこれが一番速い場合もある。

関連知識

エラトステネスの篩

$n$ 未満の全ての素数を洗い出すアルゴリズム。
判定したい個数が多いなら、あちらを使った方が全体としては速い場合もある。

素因数分解

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