2026-09-24
count_distinct_prime_factors.rs
fn count_distinct_prime_factors(mut n: u64) -> u32 {
}
整数nを素因数分解したとき、指数を無視して異なる素数が何種類現れるかを返すcount_distinct_prime_factorsを書いてください。n = 1のときは素因数を持たないので0です(境界)。count_distinct_prime_factors(1) → 0。count_distinct_prime_factors(360) → 3(360 = 2^3 * 3^2 * 5で、種類は2, 3, 5の3つ)。count_distinct_prime_factors(17) → 1(17自身が素数)。
Reference
fn count_distinct_prime_factors(mut n: u64) -> u32 {
let mut count = 0u32;
let mut p = 2u64;
while p * p <= n {
if n.is_multiple_of(p) {
while n.is_multiple_of(p) {
n /= p;
}
count += 1;
}
p += 1;
}
if n > 1 {
count += 1;
}
count
}
試し割り法そのものはfactorizeと同じですが、指数を記録する代わりに、そのpで少なくとも1回割り切れたかどうかだけを見てcountを1つ増やします。内側のwhile n.is_multiple_of(p)ループは指数の数だけnを割り続けますが、countへの加算は外側のifが真になった1回だけ行われるので、360 = 2^3 * 3^2 * 5のように指数が2以上あっても、その素数は1種類としてしか数えられません。ループを抜けたあとに残っているnが1より大きければ、それ自身が(それより小さい素因数では割り切れなかった)最後の素因数なので、忘れずに1つ加えます。これは参考実装であり、唯一の正解ではありません。