Smallest value after replacing with sum of prime factors

Math Simulation Number Theory

49.8% acceptance

Feb 25, 2026

455

You are given a positive integer n. Continuously replace n with the sum of its prime factors. Note that if a prime factor divides n multiple times, it should be included in the sum as many times as it divides n. Return the smallest value n will take on.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_value(mut n: i32) -> i32 {
    loop {
      let mut m = n;
      let mut s = 0;
      let mut d = 2;
      while d * d <= m {
        while m % d == 0 {
          s += d;
          m /= d;
        }
        d += 1;
      }
      if m > 1 {
        s += m;
      }
      if s == n {
        return n;
      }
      n = s;
    }
  }
}