Problem

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 valuen will take on.

Examples

Example 1

1
2
3
4
5
6
7

Input: n = 15
Output: 5
Explanation: Initially, n = 15.
15 = 3 * 5, so replace n with 3 + 5 = 8.
8 = 2 * 2 * 2, so replace n with 2 + 2 + 2 = 6.
6 = 2 * 3, so replace n with 2 + 3 = 5.
5 is the smallest value n will take on.

Example 2

1
2
3
4

Input: n = 3
Output: 3
Explanation: Initially, n = 3.
3 is the smallest value n will take on.

Constraints

  • 2 <= n <= 10^5

Solution

Method 1 – Iterative Prime Factor Summing

Intuition

At each step, replace n with the sum of its prime factors (counting multiplicity). If n is already prime, it will not change. The process always converges to a prime, which is the smallest value n will take on.

Approach

  1. While n is not equal to the sum of its prime factors:
    • Compute the sum of all prime factors of n (with multiplicity).
    • If the sum equals n, break (n is prime).
    • Otherwise, set n to the sum and repeat.
  2. Return n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int smallestValue(int n) {
        while (true) {
            int x = n, s = 0, d = 2;
            while (x > 1) {
                while (x % d == 0) { s += d; x /= d; }
                d++;
                if (d * d > x) d = x;
            }
            if (s == n) break;
            n = s;
        }
        return n;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func smallestValue(n int) int {
    for {
        x, s, d := n, 0, 2
        for x > 1 {
            for x%d == 0 { s += d; x /= d }
            d++
            if d*d > x { d = x }
        }
        if s == n { break }
        n = s
    }
    return n
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int smallestValue(int n) {
        while (true) {
            int x = n, s = 0, d = 2;
            while (x > 1) {
                while (x % d == 0) { s += d; x /= d; }
                d++;
                if (d * d > x) d = x;
            }
            if (s == n) break;
            n = s;
        }
        return n;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun smallestValue(n0: Int): Int {
        var n = n0
        while (true) {
            var x = n; var s = 0; var d = 2
            while (x > 1) {
                while (x % d == 0) { s += d; x /= d }
                d++
                if (d * d > x) d = x
            }
            if (s == n) break
            n = s
        }
        return n
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def smallestValue(self, n: int) -> int:
        while True:
            x, s, d = n, 0, 2
            while x > 1:
                while x % d == 0:
                    s += d
                    x //= d
                d += 1
                if d * d > x:
                    d = x
            if s == n:
                break
            n = s
        return n
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn smallest_value(mut n: i32) -> i32 {
        loop {
            let (mut x, mut s, mut d) = (n, 0, 2);
            while x > 1 {
                while x % d == 0 { s += d; x /= d; }
                d += 1;
                if d * d > x { d = x; }
            }
            if s == n { break; }
            n = s;
        }
        n
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    smallestValue(n: number): number {
        while (true) {
            let x = n, s = 0, d = 2;
            while (x > 1) {
                while (x % d === 0) { s += d; x /= d; }
                d++;
                if (d * d > x) d = x;
            }
            if (s === n) break;
            n = s;
        }
        return n;
    }
}

Complexity

  • ⏰ Time complexity: O(sqrt(n) * log n), since each prime factorization takes O(sqrt(n)), and n decreases rapidly with each step.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.