perl で効率の良い素因数分解の方法

質問

以下は、N を素因数分解し、それにかかる時間を表示するプログラムです。

#!/usr/bin/perl -w
use Benchmark;
print("N=?");
chomp($n=<STDIN>);
$start_time=new Benchmark;
$i=2;
while($i <= $n){
if($n%$i==0){
print("$i、");
$n = $n/$i;
}else
{$i++;
}
}
$end_time=new Benchmark;
$time=timediff($end_time,$start_time);
print("このプログラムの実行時間は".timestr($time)."秒です。\n");

確かに、このプログラムを用いれば、入力した数字を素因数分解し、それにかかった時間を表示させることができます。
しかしこの方法では、数字が大きくなると計算に時間がかかってしまい、効率がかなり悪くなってしまいます。
ヒントだけでも良いので、どなたかもっと効率の良い方法を教えていただけませんか。

よろしくお願い致します。

回答No.3

ramayana

ANo.1さんが紹介しているρ法が、速いし、プログラミングも簡単です。

ただ、Nが素数のときに無限ループに陥るので、素数判定のルーチン（Miller-Rabin法など）と組み合わせて使うことになります。

回答No.2

中村 拓男（@tknakamuri）

定石ですけど n の平方根より大きな i を
調べる必要はないです。

平方根より大きな i で割り切れれば、
その商は平方根より小さくなり、
その商で割り切れるはずだからです。

これだけで劇的に速くなりますよ。

後、6以上では 6で割って 1, 5 以外は
素数ではないから、調べる量を 1/3 に出来ます。

回答No.1

Tacosan

ρ法とか数体ふるい法とかあるけど...

とりあえず
・2以外の素数は奇数であることを使うと調べるべき数は半分くらいに減る (2 と 3 以外の素数は 6n±1 と書けることを使えば 1/3 くらいになる)
・while の条件は緩すぎ
という指摘だけしておこう.