概要
素数判定のプログラムを書くことを考えます。
素朴な実装をすると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)の計算量のアルゴリズムです。
高速化
素数判定では、「合成数 は を満たす素因子 をもつ」という性質を利用します。
合成数とは、素数でない数のことです。
例えば 36 の場合、「合成数 は を満たす素因子をもつ」。
つまり、36は6以下の素因子を持つことを意味します(p=2,3,4,6)。
36の素因子は12や18もありますね。
しかし、36が素数かどうか判定する場合は、6以下の整数の中に素因子があるかどうかを調べれば良いことになります。
つまりプログラム上では、 (素朴な方法)まで調べる必要はなく、 まで調べれば良いことになります。
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; }
このアルゴリズムは、 の計算量になります。
証明
「合成数 は を満たす素因子 をもつ 」
という性質の証明は以下のとおりです。
が合成数の場合、1でない整数 が存在して、 とかける。
ここで、 とすると、
(1) 両辺を2乗して、 p2 > n
(2) から、 p2
(1)、(2) から、
p2 > n
となり矛盾するため、
はそれ自体が素数か、p未満の素因数を持つため、
以下の素因数を持つ。
よって、 より、 は 以下の素因数を持つ。