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万とかまとまって素数判定をしないと、
実行時間の比較ができないから行っている。
そう考えると、奇数だけ考えるとかはちょっとおかしい。
実行時間に大差はないと思うが、
次回はその辺も考慮に入れる。