$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

1e7 までの素数が 1e6 個あるとすると， 方法1では4秒，方法2では 8秒，方法3では 0.78秒，方法4では 0.47秒． 1e6 までの素数が 1e4 個だと， 方法1では4秒，方法2では 8秒，方法3では 0.78秒，方法4では 0.47秒． 15ミリ秒，方法2では30ミリ秒，方法3では 4ミリ秒，方法4では 7ミリ秒．

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