# Smallest Value After Replacing With Sum of Prime Factors **Difficulty:** MEDIUM [External](https://leetcode.com/problems/smallest-value-after-replacing-with-sum-of-prime-factors) Canonical: https://scaleengineer.com/dsa/problems/smallest-value-after-replacing-with-sum-of-prime-factors **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory) --- ## 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 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 <= 105` # Approaches ## Naive Trial Division This approach directly simulates the process by repeatedly calculating the sum of prime factors and updating the number. For the factorization step, it uses a basic and inefficient trial division method where potential factors are checked up to the number itself. **Time:** O(K * N), where K is the number of iterations until convergence and N is the value of the number. In the worst case, factorizing a large prime N takes O(N) time. Since K is small, the complexity is dominated by the factorization of the initial input `n`. · **Space:** O(1) extra space. **Pros:** Conceptually simple and easy to implement. **Cons:** Highly inefficient, especially for large prime numbers or numbers with large prime factors.; The time complexity for factorizing a single number `k` can be up to `O(k)`, which is very slow for the given constraints. ### Explanation The core of this method is a loop that continues until the number `n` stabilizes. A number stabilizes when it is equal to the sum of its own prime factors (e.g., a prime number or 4). The value of `n` is guaranteed to converge because the sum of prime factors of a composite number (other than 4) is strictly less than the number itself, leading to a decreasing sequence. The factorization is performed naively. For a number `k`, we start checking for divisibility from `d = 2`. If `k` is divisible by `d`, we add `d` to our sum and divide `k` by `d`, repeating this until it's no longer divisible. Then we move to the next potential divisor `d+1`. This process continues until the number is reduced to 1. ```java class Solution { public int smallestValue(int n) { while (true) { int sumOfPrimeFactors = getSumOfPrimeFactors(n); if (sumOfPrimeFactors == n) { break; } n = sumOfPrimeFactors; } return n; } private int getSumOfPrimeFactors(int k) { if (k <= 3) { // Base cases for small primes return k; } int sum = 0; int temp_k = k; int d = 2; while (temp_k > 1) { if (temp_k % d == 0) { sum += d; temp_k /= d; } else { d++; } } return sum; } } ``` ### Algorithm - The main function `smallestValue(n)` operates in a loop. - In each iteration, it computes the sum of prime factors of the current `n` by calling a helper function, `getSumOfPrimeFactors(n)`. - The helper function finds prime factors by trial division, iterating a potential divisor `d` from 2 upwards. For a given number `k`, this check can go up to `k` itself. - The loop continues to divide the number by `d` as long as it is divisible, adding `d` to a running sum. - If the divisor `d` is not a factor, it is incremented. - The main loop checks if the calculated sum is equal to the current `n`. If they are equal, a fixed point is reached, and `n` is returned. - Otherwise, `n` is updated to the new sum, and the loop continues. ## Sieve of Eratosthenes Precomputation This approach uses the Sieve of Eratosthenes to precompute the smallest prime factor for every number up to the given constraint. This precomputation allows for very fast factorization of any number in the range. While each factorization is quick, the initial setup time and space usage are considerable. **Time:** O(MAX_N * log(log(MAX_N)) + K * log(N)). The precomputation time dominates for a single call, making it less efficient than the optimized trial division approach in this specific problem context. · **Space:** O(MAX_N), where MAX_N is the upper limit for the sieve (100001 in this case). **Pros:** Extremely fast factorization (`O(log n)`) after the initial setup.; Very efficient if the `smallestValue` function were to be called multiple times with different inputs. **Cons:** Requires a large amount of extra space for the SPF array, `O(MAX_N)`.; Incurs a significant upfront time cost for the sieve precomputation, which makes it slower than the optimized trial division for a single function call. ### Explanation The main idea is to trade space and a one-time precomputation cost for faster subsequent calculations. We first create an array, `spf`, of size `100001`. We initialize `spf[i] = i`. Then, we iterate from 2 upwards. When we find a prime number `p` (where `spf[p] == p`), we iterate through its multiples `j` and set `spf[j] = p` if `j`'s smallest prime factor hasn't been found yet. This fills the `spf` array in `O(MAX_N * log(log(MAX_N)))` time. Once the `spf` array is ready, calculating the sum of prime factors for a number `k` is efficient. We just repeatedly add `spf[k]` to our sum and update `k` to `k / spf[k]` until `k` becomes 1. This factorization takes only `O(log k)` time. The overall simulation loop remains the same. ```java class Solution { private static final int MAX_N = 100001; private static final int[] spf = new int[MAX_N]; static { for (int i = 0; i < MAX_N; i++) { spf[i] = i; } for (int i = 2; i * i < MAX_N; i++) { if (spf[i] == i) { // i is a prime number for (int j = i * i; j < MAX_N; j += i) { if (spf[j] == j) { // if spf[j] is not set yet spf[j] = i; } } } } } public int smallestValue(int n) { while (true) { int sumOfPrimeFactors = getSumOfPrimeFactors(n); if (sumOfPrimeFactors == n) { break; } n = sumOfPrimeFactors; } return n; } private int getSumOfPrimeFactors(int k) { if (k < 4) return k; int sum = 0; int temp_k = k; while (temp_k > 1) { sum += spf[temp_k]; temp_k /= spf[temp_k]; } return sum; } } ``` ### Algorithm - A one-time precomputation step is performed to build a Smallest Prime Factor (SPF) array for all numbers up to a maximum limit (e.g., 100001). - This is done using a Sieve of Eratosthenes variant, which populates `spf[i]` with the smallest prime that divides `i`. - The main `smallestValue(n)` function then enters a loop that continues until `n` stabilizes. - In each iteration, it calls a helper function `getSumOfPrimeFactors(n)` that uses the precomputed `spf` array. - This helper function calculates the sum by repeatedly dividing `n` by its smallest prime factor (`spf[n]`) and adding that factor to a sum, until `n` becomes 1. - The main loop terminates when the sum equals `n`, returning the final value. ## Optimized Trial Division This approach refines the factorization step by using an optimized trial division method. Instead of checking for divisors all the way up to `n`, it only checks up to `sqrt(n)`. This is based on the property that any composite number `n` must have a prime factor less than or equal to `sqrt(n)`. This optimization makes the process significantly faster without requiring extra space. **Time:** O(K * sqrt(N)), where K is the number of iterations and N is the initial input value. Since K is very small, the effective complexity is `O(sqrt(N))`, which is the most efficient for a single call. · **Space:** O(1) extra space. **Pros:** Very time-efficient for the given constraints.; Requires no extra space, making it memory-efficient.; Strikes a good balance between implementation complexity and performance. **Cons:** Slightly more complex to write than the naive trial division. ### Explanation The overall iterative structure to find the smallest value remains unchanged. The efficiency gain comes from the prime factorization logic. For any number `k`, we can find its prime factors by checking for divisibility only up to `sqrt(k)`. The algorithm proceeds as follows: 1. In a loop, calculate the sum of prime factors for the current `n`. 2. To get the sum, we iterate `i` from 2 up to `sqrt(n)`. 3. For each `i`, we check if it divides `n`. If it does, we add `i` to a running sum and divide `n` by `i` repeatedly until it's no longer divisible. 4. After the loop finishes, if `n` has been reduced but is still greater than 1, the remaining `n` is a prime factor itself and is added to the sum. 5. The main loop replaces the original `n` with this sum and repeats until the sum is equal to `n`. This method is highly efficient for the given constraints and does not have the large space or precomputation overhead of the sieve method. ```java class Solution { public int smallestValue(int n) { while (true) { int sumOfPrimeFactors = getSumOfPrimeFactors(n); if (sumOfPrimeFactors == n) { break; } n = sumOfPrimeFactors; } return n; } private int getSumOfPrimeFactors(int k) { int sum = 0; int n = k; // Find all factors of 2 while (n % 2 == 0) { sum += 2; n /= 2; } // Find factors for odd numbers for (int i = 3; i * i <= n; i += 2) { while (n % i == 0) { sum += i; n /= i; } } // If n is still > 1, it must be a prime number if (n > 1) { sum += n; } // If k was prime initially, sum will be k. If k was 4, sum will be 4. return sum; } } ``` ### Algorithm - The main `smallestValue(n)` function works in a loop, same as the other approaches. - The key improvement is in the `getSumOfPrimeFactors(n)` helper function. - To factorize a number `k`, it iterates through potential divisors `d` only up to `sqrt(k)`. - It first handles all factors of 2 separately. - Then, it iterates through odd numbers `d` from 3 up to `sqrt(k)`. - For each `d`, it repeatedly divides `k` and adds `d` to the sum. - After the loop, if the remaining value of `k` is greater than 1, this remaining value must be a prime factor itself, so it's added to the sum. - The main loop continues this process until `n` converges to a fixed point. # Solutions ### Java ```java class Solution { public int smallestValue(int n) { while (true) { int t = n, s = 0; for (int i = 2; i <= n / i; ++i) { while (n % i == 0) { s += i; n /= i; } } if (n > 1) { s += n; } if (s == t) { return s; } n = s; } } } ``` ### CPP ```cpp class Solution { public: int smallestValue(int n) { while (1) { int t = n, s = 0; for (int i = 2; i <= n / i; ++i) { while (n % i == 0) { s += i; n /= i; } } if (n > 1) s += n; if (s == t) return s; n = s; } } }; ``` ### Python ```python class Solution: def smallestValue(self, n: int) -> int: while 1: t, s, i = n, 0, 2 while i <= n // i: while n % i == 0: n //= i s += i i += 1 if n > 1: s += n if s == t: return t n = s ```