Brute Force Method

ある数ｎの素因数を求める時、一番最初に思いつく方法は、小さい数から順に割っていく方法である。

アルゴリズム１

１)２で n を割り切れなくなるまで割る。
２)３で n を割り切れなくなるまで割る。
３)４で n を割り切れなくなるまで割る。
・
・
・
nが完全に素因数分解できるまで試す。

アルゴリズム２

１)２で n を割り切れなくなるまで割る。
２)３で n を割り切れなくなるまで割る。
３)２で n を割り切れなくなるまで割っているので、以下奇数で割っていく。
・
・
・
nが完全に素因数分解できるまで試す。

アルゴリズム３

上の方法で、３より大きい奇数について、３で割り切れるものは試行対象とする必要がないので除去する。
つまり、２×３＝６以下の素数２、３、５についてはそのまま割り算。
６以上については、6n＋１、6n＋５のみを割り算の対象とする。
nが完全に素因数分解できるまで試す。

結論

ならば、５も７も１１も……、というようにいくらでも効率化できるが、この方法を押し進めていっても、試行対象のｐの増え方は、素数定理よりｎlog(n)のオーダなので、あまり大きなｐを検出することはできない。
違うアイデアを考えよう。