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);
}