プログラミングのお題スレ Part22 (854ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
738(7): デフォルトの名無しさん [sage] 2025/04/08(火) 23:28:40.30 ID:OzdBhfzQ(1/2) AAS
>>712712(4): デフォルトの名無しさん [] 2025/03/28(金) 21:33:35.13 ID:VDfNaTNz(1/3) AAS
お題：素因数の総和が2025である2000万以下の自然数をすべて求めて下さい。
例)
32272
素因数分解すると32272 = 2 × 2 × 2 × 2 × 2017で、
素因数の総和は2 + 2 + 2 + 2 + 2017 = 2025となります。
※20億以下でもC++で5秒以内に余裕で完了できますが、出力が長すぎるため2000万以下としました。
その結果、Rでも5秒以内に余裕で完了できる問題になりました。
Rust
fn solve(n: usize, limit: usize) -> Vec<usize> {
let mut answer = Vec::new();
let mut pnt = generate_primes(n).iter().skip(1).rev().map(|&p| (p, 0, 0)).collect::<Vec<_>>();
let (mut ci, mut cn, mut ct) = (0, n, 1_usize);
'advance: loop {
pnt[ci..].iter_mut().for_each(|(_p, n, t)| (*n, *t) = (cn, ct));
if cn & 1 == 0 && ct.leading_zeros() >= (cn >> 1) as u32 {
ct <<= cn >> 1;
if ct <= limit { answer.push(ct as usize); }
}
for (i, (p, n, t)) in pnt.iter_mut().enumerate().rev() {
if *n < *p { continue; }
*n -= *p; *t *= *p;
if *t > limit { continue; }
if *n == 1 { continue; }
if *n == 0 { answer.push(*t as usize); continue; }
(ci, cn, ct) = (i, *n, *t);
continue 'advance;
};
break;
}
answer.sort(); answer
}
739(3): デフォルトの名無しさん [sage] 2025/04/08(火) 23:30:40.48 ID:OzdBhfzQ(2/2) AAS
>>738
素因数の総和が2025になる問題を可能な素数の組合せ総当りで挑戦してみました
20億以下で約0.4秒と規定時間以内に実行できました
実行時間 solve(2025, 20000000): 22.638309ms
実行時間 solve(2025, 2000000000): 418.607978ms
fn main() {
for (n, limit) in [(2025, 2000_0000), (2025, 20_0000_0000)] {
let start_time = std::time::Instant::now();
let answer = solve(n, limit);
let end_time = std::time::Instant::now();
println!("実行時間 solve({n}, {limit}): {:?}", end_time - start_time);
// 個数と最初と最後の検証
let (valid_len, valid_first, valid_last) = match (n, limit) {
(2025, 2000_0000) => (1265, 30255, 19970000),
(2025, 20_0000_0000) => (49942, 30255, 1999986740),
_ => (0, 0, 0),
};
assert_eq!(answer.len(), valid_len);
assert_eq!(*answer.first().unwrap(), valid_first);
assert_eq!(*answer.last().unwrap(), valid_last);
}
}
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.449s*