プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
741(4): デフォルトの名無しさん [] 04/09(水)22:22 ID:Ip5PiQSs(1/3)
>>738-739
出題時に作成した解答例
C++
https://ideone.com/y1YZlj
R
https://ideone.com/zvqAsg
と解の個数と最小値・最大値が一致するので正解だろう。
ローカルでコンパイルしようとしたら、
error[E0425]: cannot find function `generate_primes` in this scope
と表示されコンパイルできなかったので、実行時間の比較はできなかった。
742: デフォルトの名無しさん [sage] 04/09(水)22:57 ID:R3DmBa+t(1/3)
>>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()
}
743(1): デフォルトの名無しさん [] 04/09(水)23:40 ID:Ip5PiQSs(2/3)
>>738-739 742と>>741のC++を解の標準出力なしに変更したものの実行速度を比較したら、
前者の方が2000万以下では27%、20億以下では11%速かった。
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秒)
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.026s