プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
754(2): デフォルトの名無しさん [] 04/12(土)21:18 ID:RVQAocGC(1)
>>741のC++プログラムは for (int i = S; i >= 2; i--) のループの最後のi = 2の場合を
ループの外に出して最適化 (p[S]以外のp[_]への要素追加をしないように) するだけで、
20億以下で解の出力なしのときの実行時間が元のプログラムの半分未満になるな。
https://ideone.com/RtTEO2 (1.02秒)
↓
https://ideone.com/1O04wl (0.44秒)
755: デフォルトの名無しさん [sage] 04/12(土)21:26 ID:csJOBVaF(1)
>>754
それに気づいたけど
まだ>>750と比べて20倍遅いからメモ化の方針が徒となってるのかな
760: デフォルトの名無しさん [sage] 04/17(木)00:29 ID:dz0qzhSq(2/3)
>>741
2000万個すべてを素因数分解する方法とは逆に、
2025以下の素数の組み合わせを調べていく方法。
そのうち和が2025になる組み合わせの積が各解となる。
それを効率よく求めるために2025(+1)個のベクタのベクタpを用意している。
つまり和がsumとなる時の積をp[sum]に記録していく。
効率面からの仮の初期値p[0]に1を入れて、各素数iについて降順に、
ベクタp[j]にxがある時、ベクタp[i+j]にx*iをpushしていく。
ここでjの上限は 2025 - i、処理するxの上限は 2000万 / i の枝刈りができる。
最終的にベクタp[2025]の一覧が解となる。
2025個のベクタを用いることが長所および短所になっている。
この改良版>>754では、最後の素数2だけ特別扱いすることで倍速にしている。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.024s