11/11/28 12:49:12.45
>>850
【モリタポ有償】C/C++の問題を片付けます(2)
URLﾘﾝｸ(hibari.2ch.net)
534 名前： ◆QZaw55cn4c [qzaw55cn4c@a.email.ne.jp] 投稿日：2011/04/25(月) 21:03:10.67
>>516
URLﾘﾝｸ(codepad.org)
ｽﾚﾘﾝｸ(tech板:439番) の指摘を受けて細かいところを変更しました。
＞素数の調べ方がクソ
エラトステネスのふるいは必要なメモリ容量が半端でないので、「クソ」かもしれませんが、素朴な方法にしました。10万までなら、（私の環境では）十分な速度が出ています。
しかし、割り算を二回実行してしまうのはなんとかしたいと思いつつも改良できないでいます。
＞ループにも無駄が多すぎ
ちょっとだけましになったと思います。
592 名前：581 ◆QZaw55cn4c [PhenomII x6 が放置状態‥‥] 投稿日：2011/04/27(水) 05:53:22.39
>>591
＞for(i = 2, max_len = 0; i * max_len < N; i++) {
を説明していただけませんでしょうか。
ベルトランの仮説（チェビシェフにより証明）を利用していると思われるんですが、
i から 2i の間に素数があっても、2i から 3i の間に素数があるかどうかはわかりません。
もっともここを
for (i = 2, i < N; i++)
にしてみたところで、
URLﾘﾝｸ(codepad.org)
爆速なんですけれども。（それか、codepad を速度判定に用いるのは精度がよくないですね。）
それにしてもエラトステネスのふるいの威力は見損じていました。sierve[i] で素数判定できるのには太刀打ちできません。
削除申請を出しました。
ｽﾚﾘﾝｸ(saku板:337番)