You are given a positive integer n.
Continuously replace n with the sum of its prime factors.
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.
Example 1:
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:
Input: n = 3 Output: 3 Explanation: Initially, n = 3. 3 is the smallest value n will take on.
Constraints:
2 <= n <= 105The key idea in #2507 Smallest Value After Replacing With Sum of Prime Factors is to repeatedly replace a number n with the sum of its prime factors (counted with multiplicity). This process continues until the value no longer changes. The problem can be treated as a simulation with prime factorization.
For each step, compute the prime factors of n using trial division. Iterate from 2 up to sqrt(n) and accumulate the factors while dividing them out. If a remainder greater than 1 remains, it is also a prime factor. After computing the sum, replace n with this value and repeat the process until the sum equals the current value, indicating a stable result.
This iterative reduction works because composite numbers typically shrink when replaced by the sum of their prime factors. Each factorization step costs about O(sqrt(n)), and the process runs only a small number of iterations in practice, making the simulation efficient.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative Simulation with Prime Factorization | O(k * sqrt(n)) where k is the number of iterations | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Every time you replace n, it will become smaller until it is a prime number, where it will keep the same value each time you replace it.
n decreases logarithmically, allowing you to simulate the process.
To find the prime factors, iterate through all numbers less than n from least to greatest and find the maximum number of times each number divides n.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
The process stops when the sum of prime factors equals the current number. This typically happens when the number becomes prime, because a prime number’s only prime factor is itself.
Yes, this type of number theory and simulation problem appears in technical interviews. It tests understanding of prime factorization, loops, and efficient mathematical reasoning.
No complex data structure is required for this problem. Simple integer variables and loops are sufficient since the main task is repeated prime factorization and summation.
The optimal approach simulates the process by repeatedly computing the sum of prime factors of the current number. Using trial division up to the square root efficiently finds all factors. The process stops when the value no longer changes.