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で止まります。