素数の数(2)

ずいぶん間が空いてしまったが、
方針を変えてやっていく。


基本的には、
ある自然数nに対して、
n 〜 n + dn
素数の数を求めるのに、
どうすれば速くなるかを考えるようにする。


今考えているのは、
前回参照した本に書いてあった3段階で素数判定する方法で、
ここには2ヶ所パラメータがあるが、
そのパラメータを n ごと最適化する。
要するに、n の関数にする。
(dnは一定とするが、まだ具体的には考えていない)


懸念されるのは、
32ビット整数の範囲では、
単純に素数で割っていったほうが速いのでは、
ということである。
(あまり多くの素数を保持するのもなんなので、
奇数で割っていくでいいかもしれない)
その場合は、64ビットの整数を使っていく。
それでもやっぱり単純なアルゴリズムが速い場合は、
自作の長整数クラスを使っていくことになってしまう。


その場合は、
除算のアルゴリズムをなんとかしなければならない。
今までのは非常に遅いので。
なかなか難しいが、色々考えてはいる。