素数判定

概要

素数判定のプログラムを書くことを考えます。
素朴な実装をするとO(n)の計算量になってしまうので、
高速化することを考える必要があります。

素朴な実装

素朴な実装では、与えられた整数xが2からx-1までの数で割り切れるかどうかを順番に調べます。

int isPrime(int x)
{
  if (x <= 1) return 0;

  if (x == 2) return 1;

  for (int i=2; i<x; i++) {
    if (x % i == 0) return 0;
  }

  return 1;
}

これはO(n)の計算量のアルゴリズムです。

高速化

素数判定では、「合成数  x x \leq sqrt(x) を満たす素因子  p をもつ」という性質を利用します。
合成数とは、素数でない数のことです。

例えば 36 の場合、「合成数  36 p \leq sqrt(36) を満たす素因子 pをもつ」。
つまり、36は6以下の素因子を持つことを意味します(p=2,3,4,6)。
36の素因子は12や18もありますね。
しかし、36が素数かどうか判定する場合は、6以下の整数の中に素因子があるかどうかを調べれば良いことになります。

つまりプログラム上では、 x-1 (素朴な方法)まで調べる必要はなく、  sqrt(x) まで調べれば良いことになります。

int isPrime(int x)
{
  if (x <= 1) return 0;

  if (x == 2) return 1;

  for (int i=2; i<sqrt(x); i++) {
    if (x % i == 0) return 0;
  }

  return 1;
}

このアルゴリズムは、 O(sqrt(n)) の計算量になります。

証明

合成数  x x \leq sqrt(x) を満たす素因子  p をもつ 」
という性質の証明は以下のとおりです。

 n合成数の場合、1でない整数 p,q (p \leq q) が存在して、 n=pq とかける。

ここで、 p \gt sqrt(n) とすると、

(1) 両辺を2乗して、 p2 > n
(2)  p \leq q から、  pq \geq p2

(1)、(2) から、  pq \geq p2 > n
となり矛盾するため、
 p \leq sqrt(n)

 pはそれ自体が素数か、p未満の素因数を持つため、
 sqrt(n) 以下の素因数を持つ。

よって、  n=pq より、  n sqrt(n) 以下の素因数を持つ。

参考

素数判定 | アルゴリズムとデータ構造 | Aizu Online Judge

detail.chiebukuro.yahoo.co.jp