11/11/28 12:50:06.13
614 名前： ◆QZaw55cn4c [sage] 投稿日：2011/04/27(水) 07:54:07.83
>>599
最初の素数 p があったとして、その次が 2p までにあることはベルトランの仮説により証明されているようです。まあ実際は、素数はもっと詰まっていますが。
p と len_max の二つの情報にベルトランの仮説を用いて探索範囲を狭めるのならば、p * (2^(len_max - 1) < i でしょうね。(^ はここではべき乗）
素数の間隔に関する単純な定理が他にあるかどうかは、調べてみましたがよくわかりませんでした。素数分布に関するものならいくつかありますが。
617 名前： ◆QZaw55cn4c [sage] 投稿日：2011/04/27(水) 08:08:33.63
>>610
i の探索範囲が狭まると、狭まった分だけループの回数が減りますが、本当に減らしてもいいのでしょうか、という問題です。
たしかに実質 >>602 で len_max 個分の隣り合う素数を足しこんで N 以上であれば打ち切っていますが、これは実際にスキャンして調べているわけでその分計算量を要しています。
でも、だからといって、i * len_max が N を超えたら実際に調べなくともいい、とは限らないと考えています。
>>592 で影響の度合いの確認はとっています。