Namaran

Code daily. Without assist.

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つ加えます。これは参考実装であり、唯一の正解ではありません。