素因数分解

コメント欄でご指摘いただいたことを考えてみます．素因数分解をする際に素数の列として，エラトステネスの篩ではなく，

primes = 2:3:([6,12..] >>= (\x->[x-1,x+1] )

を使うというテクニック．6の倍数の「前後」を「素数のタネ」として使うということです．6というのはちょっと特異で，約数が1，2，3，6と「6」という大きさに対してたくさんあります，そのため，6で割った余りで自然数を6n，6n+1，6n+2，6n+3，6n+4，6n+5と分類した場合，偶数もしくは3の倍数ではない数は，6n+1と6n+5の二つしかありません．したがって，素数は6で割れば，余りが1か5であり，6の倍数に1を足すか引くかすれば表現できることになります．ただしこれは，2と3という例外があります．

さて，こうして得られた「列」を素因数分解の「タネ」とするわけですが，もちろんこの「列」には素数以外の数字もたくさんあります．しかし，それらの数はかならず約数をもっており，また「下から素数を探す」ということをすれば，その「素数以外の数」はすでに，もともとの対象の数の「約数ではない」ので素因数としては現われないのです．

したがって，明らかに計算コストはエラトステネスの篩よりも低くなるはずです．

Project EulerのProblem 3の実行時間を計測してみました
実行コマンドはbashで * には1，2，3が入ります．

time ./prime*  600851475143

1，2，3の意味は以下の通り．

• prime1：エラトステネスの篩
• prime2：6の倍数の前後の列
• prime3：単純なロー法

結果は

	*real	*user	*sys
prime1	0m0.151s	0m0.040s	0m0.036s
prime2	0m0.019s	0m0.000s	0m0.020s
prime3	0m0.020s	0m0.000s	0m0.012s

となりました．prime2，3は微妙ですが，明らかに，エラトステネスの篩はコストが高いです．

これだけだとちょっと差が見にくいので，フェルマー数で計算させてみます．方法と記法は同じです．

	*real	*user	*sys
prime1	---	---	---
prime2	0m1.888s	0m1.620s	0m0.232s
prime3	0m0.059s	0m0.032s	0m0.020s

prime1（エラトステネスの篩）に関しては，実行時間があまりに長いので中断させました．prime2もエラトステネスの篩に比べて圧倒的，ロー法はさらに圧倒的な速さです．