Namaran

Code daily. Without assist.

2026-09-24

drop_squarefree.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 drop_squarefree_factors(factors: &mut Vec<(u64, u32)>) {
    for i in 0..factors.len() {
        if factors[i].1 == 1 {
            factors.remove(i);
        }
    }
}

fn main() {
    let mut factors = factorize(420);
    drop_squarefree_factors(&mut factors);
    for (p, e) in &factors {
        print!("{p}^{e} ");
    }
    println!();
}

素因数分解の結果(素数, 指数)のVecから、指数が1の素因数(平方因子でない素数)だけを取り除くつもりの関数です。入力はfactorize(420)の結果、つまり(2,2), (3,1), (5,1), (7,1)。いまの出力は保証されません(このコードは実行すると、範囲外アクセスで必ずpanicして異常終了するため、想定していた出力は一切表示されません)。本来の出力は2^2 (末尾に半角スペース、そのあとに改行)です。何が問題で、どう直せばよいでしょうか?

Answer

factors.remove(i)は指定した位置の要素を取り除き、それより後ろの要素を1つずつ前へ詰めます。ところがfor i in 0..factors.len()の範囲は、ループが始まる前の長さ(ここでは4)でいったん固定されてしまい、要素を削除してVecが縮んでもiの刻み方は変わりません。トレースすると: i = 0で(2,2)は指数2なのでそのまま。i = 1で(3,1)を削除すると、後ろにあった(5,1)が位置1に、(7,1)が位置2に詰まります。次はi = 2に進むので、詰まったことで位置1に来た(5,1)は一度も調べられないまま素通りされ、代わりに位置2の(7,1)が削除されます。この時点でVecの長さは2しかないのに、ループはまだi = 3を回そうとするため、factors[3]で範囲外アクセスとなりpanicします。削除のたびに縮んでいくVecを、縮む前の長さぶんインデックスで回し続けたことが原因です。直し方は、条件を満たす要素だけを残すretainを使い、インデックスの管理そのものをなくすことです:

fn drop_squarefree_factors(factors: &mut Vec<(u64, u32)>) {
    factors.retain(|&(_, e)| e != 1);
}