[過去ﾛｸﾞ] 【モリタポ有償】C/C++の問題を片付けます(2) (1001ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
611: 2011/04/27(水)07:46 AAS
なんで俺が恥をさらした部分に食いつくのか。。。
それよりさらに速くなったことについて感想を。。。
612: 2011/04/27(水)07:50 AAS
- for(i = 2, max_len = 0; i * max_len < N; i++) {
+ for(i = 2, max_len = 0; ; i++) {
これでおｋ。
もっとも(って好きだよね)これによって削減される演算は微々たる物ですが
613: 2011/04/27(水)07:52 AAS
必要なすべての場合を踏むのは常に前提で、
意味がない処理を省くことこそがこの手の問題の必要条件じゃね？
614: ◆QZaw55cn4c 2011/04/27(水)07:54 AAS
>>599
最初の素数 p があったとして、その次が 2p までにあることはベルトランの仮説により証明されているようです。まあ実際は、素数はもっと詰まっていますが。
p と len_max の二つの情報にベルトランの仮説を用いて探索範囲を狭めるのならば、p * (2^(len_max - 1) < i でしょうね。(^ はここではべき乗）
素数の間隔に関する単純な定理が他にあるかどうかは、調べてみましたがよくわかりませんでした。素数分布に関するものならいくつかありますが。
615: ◆QZaw55cn4c 2011/04/27(水)07:55 AAS
>>602
なるほど。
616: 2011/04/27(水)07:56 AAS
そんな難しげな理論なんて関係なく、小学生レベルの算数の話
617: ◆QZaw55cn4c 2011/04/27(水)08:08 AAS
>>610
i の探索範囲が狭まると、狭まった分だけループの回数が減りますが、本当に減らしてもいいのでしょうか、という問題です。
たしかに実質 >>602 で len_max 個分の隣り合う素数を足しこんで N 以上であれば打ち切っていますが、これは実際にスキャンして調べているわけでその分計算量を要しています。
でも、だからといって、i * len_max が N を超えたら実際に調べなくともいい、とは限らないと考えています。
>>592 で影響の度合いの確認はとっています。
618: ◆QZaw55cn4c 2011/04/27(水)08:13 AAS
>>599
>最初の数字より大きいものしか続かないわけだから、i * max_len < N よりも少なくていいはず。
なるほど。やっと理解しました。
これでお開きとします。いろいろと説明ありがとうございました。
619: 2011/04/27(水)08:22 AAS
勝手に仕切ってるしw
620: 2011/04/27(水)08:24 AAS
N=100000000のとき長さ4685 （7から45161までのすべての素数の和)であってる?
621(1): 2011/04/27(水)08:31 AAS
ある素数からn個の連続が見つかったとき、それ以降のある素数からn個の連続で範囲を超えたら以後は調べる必要がない
足し算が理解できれば当たり前すぎる条件だよね
622: 2011/04/27(水)08:43 AAS
どうでもいいけど仮説ってことは証明されてないってことだよなぁ
623: 2011/04/27(水)10:33 AAS
>>596-597
10倍どころじゃなくて吹いたｗ
624: 2011/04/27(水)11:38 AAS
じゃんけんは後手必勝ｗ
625: 2011/04/27(水)13:16 AAS
砂上の空論ｗｗｗｗｗｗｗｗｗｗｗｗ
626: 2011/04/27(水)13:18 AAS
机上の楼閣の餅外じゃねｗ？
627: 2011/04/27(水)13:23 AAS
2chで金儲けっていいの？
628: 2011/04/27(水)13:29 AAS
噂には聞いていたが自己愛性人格障害ってやっぱり直らないんですね
唯一◆QZaw55cn4cが自分で白旗を揚げた点だけは評価してやろう
でも事実は>>600の通りなんだよね
こいつのアホさ加減は死ぬまで続くだろう
629: 2011/04/27(水)13:53 AAS
>>621
何でそこの話をそのタイミングでしているのか理解に苦しむ。
630(1): 2011/04/27(水)19:21 AAS
ベルトラン・チェビシェフ氏曰く「こんなどこの馬の骨ともわからん問題にいちいち私の名前を出さんどいてくれや、あほんだらが」
上下前次1-新書関写板覧索設栞歴
あと 371 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.158s*