内容別リスト/数学系/素数判定 - 競技プログラミング用 知識集積所【5/17更新】

---

雑な説明

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

レベル

ABCのC問題以降。

アルゴリズム内容

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

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

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

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

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

注意点

多数の判定には不向き。（D問題レベル）

1つめの判定結果が2つめの判定に何も役立たないため、判定したい個数が多いとそれに比例して時間がかかる。
その場合はエラトステネスの篩を使った方がよい。

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

関連アルゴリズム

エラトステネスの篩

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

素因数分解

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