$1$ 以上 $N$ 以下の整数をランダムに生成し， これらの素因数分解に要する時間を計測しました． 生成する個数は，100,000 個としました． 素因数分解の方法は以下の4通りです． 分解する整数を $x$ とします．

  1. 整数 $p = 2, 3, 4, 5, \ldots$ で順次割ってみて， 割れたら $x := x / p$ とする．$p^2 > x$ となったら打ち切り．
  2. $\lceil\sqrt{x}\;\rceil$ までの素数リストを，エラトステネスの篩で作成して， それらの素数で順次割ってみる．あとは1と同じ．
  3. 事前に $\lceil\sqrt{N}\;\rceil$ までの素数リストを， エラトステネスの篩で作成しておく． あとは2と同じ．
  4. 事前に $N$ までの整数の最小素因数リストを， 篩の方法 で作成しておく．これを用いて分解する．

測定用のソースファイル

結果は以下の通りでした．

1つの整数の素因数分解に要した時間 (単位: マイクロ秒)

N 1e5 2e5 5e5 1e6 2e6 5e6 1e7
方法1 0.70 0.89 1.19 1.56 2.03 2.97 4.02
方法2 1.13 1.53 2.21 3.04 4.18 6.85 8.73
方法3 0.25 0.30 0.36 0.42 0.50 0.65 0.78
方法4 0.09 0.10 0.10 0.16 0.21 0.28 0.33

事前計算に要した時間 (単位: ミリ秒)

N 1e5 2e5 5e5 1e6 2e6 5e6 1e7
方法3 0 0 0 0 0 0 0
方法4 0 1 2 6 22 69 147

(方法3では，N = 1e7 でも，0.02ミリ秒くらい)

1e7 以下の整数を 1e6 個素因数分解するのに要するトータルの時間は， 方法1では4秒，方法2では 8秒，方法3では 0.78秒，方法4では 0.47秒 ということになります． 1e6 以下の整数を 1e4 個だと， 方法1では16ミリ秒，方法2では30ミリ秒，方法3では 4ミリ秒，方法4では 7ミリ秒． 1e6 以下の整数を 1e5 個だと， 方法1では156ミリ秒，方法2では304ミリ秒，方法3では 42ミリ秒，方法4では 22ミリ秒．

ランダムの平均だけではなくて，最悪時間も測りたいところですが， まあ，とりあえず．