素数の数(3)

n〜n+dnの間の素数の個数を求める。
まず単純な方法でやってみた。


奇数を3から順に奇数で割っていく方法(method1)、
6で割って1か5余る数字を同じく割っていく方法(method2)、
奇数を5000までは素数表を使ってあとは奇数で割っていく方法(method3)。
こんな風になった。
Borland C++ Compiler 5.5.1
dn = 100000

n method1 method2 method3
1億 1.328s 1.327s 0.703s
10億 3.625s 3.601s 2.984s
100億 89.765s 88.232s 83.5s

あまり小手先は効かないらしい。
それから、10億と100億の間でどうしてこんなに跳ね上がるのだろう。
今はちょっと時間がないので、
またあとで調べる。
(もちろん32ビットの境界があることはわかっている)


VCでは(違うマシンだがCPUはほとんど同じ)、

n method1
1億 2.68s
10億 7.34s
100億 20.26s
1000億 54.55s

これだと自然に上がっている。
もうこっちにしようか。
VCはめんどうだけど。


あと、個数を数えているのは、
本当は個々の自然数素数判定をしたいんだけど、
10万とかまとまって素数判定をしないと、
実行時間の比較ができないから行っている。
そう考えると、奇数だけ考えるとかはちょっとおかしい。
実行時間に大差はないと思うが、
次回はその辺も考慮に入れる。