Namaran

Code daily. Without assist.

2026-09-24

factorize_trace.rs

fn factorize(mut n: u64) -> Vec<(u64, u32)> {
    let mut factors = Vec::new();
    let mut p = 2u64;
    while p * p <= n {
        if n.is_multiple_of(p) {
            let mut exp = 0u32;
            while n.is_multiple_of(p) {
                n /= p;
                exp += 1;
            }
            factors.push((p, exp));
        }
        p += 1;
    }
    if n > 1 {
        factors.push((n, 1));
    }
    factors
}

fn main() {
    for (p, e) in factorize(360) {
        print!("{p}^{e} ");
    }
    println!();
}

このプログラムを実行すると、何が出力されるでしょうか?

Answer

出力は2^3 3^2 5^1 (末尾に半角スペースが1つ入り、そのあとに改行)です。factorizeはpを2から順に試し、nがそのpで割り切れる間だけ割り続けて指数を数える、試し割り法です。360をトレースすると: p = 2のとき360は2で3回割り切れて45になり、(2, 3)を記録します。p = 3のとき45は3で2回割り切れて5になり、(3, 2)を記録します。p = 4では4 * 4 = 16がそのときのn(すでに5まで縮んでいる)より大きいのでループを抜け、残ったn = 5が1より大きいので最後に(5, 1)を追加します。ここで注目したいのは、while p * p <= nのnが入力の360ではなく、それまでに割り出した分だけ縮んだ「いまのn」だという点です。大きな素因数を取り除くたびにpの探索上限も一緒に狭まるので、本来ならsqrt(360)(約19)まで律儀に試す必要がありそうに見えて、実際にはp = 4で止まります。