Namaran

Code daily. Without assist.

2026-10-20

largest_prime.rs

fn largest_prime_factor(mut n: u32) -> u32 {
    let mut p = 2;
    let mut last = 1;
    while p * p <= n {
        while n.is_multiple_of(p) {
            n /= p;
            last = p;
        }
        p += 1;
    }
    if n > 1 { n } else { last }
}

fn main() {
    for n in [360, 97, 4_294_967_291] {
        println!("{}", largest_prime_factor(n));
    }
}

largest_prime_factor は、2以上の u32 の値 n の最大の素因数を返すつもりの関数です。main は360、97、4294967291(u32 に収まる最大の素数)の順に調べます。デバッグビルドで実行すると、いまは 5 と 97 を表示したあと、3つ目の呼び出しで panic して止まります。本来の出力は、その2行に続けて3行目に 4294967291 を表示します。

Answer

Wrong

while p * p <= n {

4294967291は素数なので、内側の while は一度も割り切れず、n は小さくなりません。外側のループは p * p <= n が偽になるまで p を増やします。p の型は、この比較から n と同じ u32 に決まっています。65535 × 65535 = 4294836225 はまだ n 以下なので p は65536まで進み、65536 × 65536 は2の32乗で、u32 の最大値4294967295を超えます。デバッグビルドの Rust は、整数の演算結果が型の範囲を超えると panic するので、ここで止まります1。

Right

while p <= n / p {

正の整数では、p * p <= n と p <= n / p は同じ条件です。n / p の小数部を切り捨てても、p が整数なので比較の結果は変わりません。割り算の結果は n を超えないので型の範囲からあふれることがなく、p が65536になったところで 65536 <= 65535 が偽になってループを抜けます。残った n は1より大きいので、4294967291がそのまま返ります。

  1. オーバーフローの検査を切ったリリースビルドでは panic せず、積は2の32乗で割った余りに回り込みます。65536 × 65536 は0になって条件が真のまま残るので、ループは本来終わるはずのところを過ぎても回り続けます。