プログラミングのお題スレ Part22 (858ﾚｽ)
プログラミングのお題スレ Part22 http://mevius.5ch.net/test/read.cgi/tech/1691038333/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
741: デフォルトの名無しさん [] 2025/04/09(水) 22:22:33.83 ID:Ip5PiQSs >>738-739 出題時に作成した解答例 C++ https://ideone.com/y1YZlj R https://ideone.com/zvqAsg と解の個数と最小値・最大値が一致するので正解だろう。 ローカルでコンパイルしようとしたら、 error[E0425]: cannot find function `generate_primes` in this scope と表示されコンパイルできなかったので、実行時間の比較はできなかった。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/741
742: デフォルトの名無しさん [sage] 2025/04/09(水) 22:57:11.84 ID:R3DmBa+t >>741 すみません 素数の一覧を返すだけなので素数列挙でもライブラリ利用でも何でもいいのですが 例えばエラトステネスの篩ならこんな感じの関数で // 素数の一覧を返す [2, 3, 5, 7, 11, ... , (最大max)] fn generate_primes(max: usize) -> Vec<usize> { // maxの平方根までの素数の倍数を篩にかければ全ての素数が見つかる let limit = max.isqrt() + 1; let mut is_prime = vec![true; max + 1]; is_prime[0] = false; is_prime[1] = false; // 偽初期値 let mut prime = 1; // 次の素数を探す (前回の素数以降でtrueを探すと次の素数) while let Some(pos) = is_prime[(prime + 1)..limit].iter().position(|bool| *bool) { prime += pos + 1; // この素数の倍数をfalseにする 【エラトステネスの篩】 is_prime[(prime << 1)..].iter_mut().step_by(prime).for_each(|bool| *bool = false); } // 素数一覧を返す (trueになるindex値が素数) is_prime.iter().enumerate().filter_map(|(index, bool)| bool.then_some(index)).collect() } http://mevius.5ch.net/test/read.cgi/tech/1691038333/742
743: デフォルトの名無しさん [] 2025/04/09(水) 23:40:58.68 ID:Ip5PiQSs >>738-739, 742と>>741のC++を解の標準出力なしに変更したものの実行速度を比較したら、 前者の方が2000万以下では27%、20億以下では11%速かった。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/743
754: デフォルトの名無しさん [] 2025/04/12(土) 21:18:53.69 ID:RVQAocGC >>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秒) http://mevius.5ch.net/test/read.cgi/tech/1691038333/754
760: デフォルトの名無しさん [sage] 2025/04/17(木) 00:29:06.02 ID:dz0qzhSq >>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だけ特別扱いすることで倍速にしている。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/760
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.049s