#2507
Smallest Value After Replacing With Sum of Prime Factors
MediumMathSimulationNumber TheorySieve of EratosthenesDynamic Programming
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n log log n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n log log n)Space O(n)
The optimal solution uses a sieve-like approach to precompute the smallest prime factor for each number up to n. This allows us to quickly find the prime factors and their sums without repeated calculations.
⚙️
Algorithm
3 steps- 1Step 1: Create an array to store the smallest prime factor for each number up to n.
- 2Step 2: Use a modified Sieve of Eratosthenes to fill this array.
- 3Step 3: For each number, repeatedly replace it with the sum of its prime factors until it becomes a prime number.
solution.py19 lines
1# Full working Python code
2
3def smallestValue(n):
4 spf = list(range(n + 1)) # Smallest prime factor
5 for i in range(2, int(n**0.5) + 1):
6 if spf[i] == i: # i is prime
7 for j in range(i * i, n + 1, i):
8 if spf[j] == j:
9 spf[j] = i
10 while n > 1:
11 sum_factors = 0
12 while n > 1:
13 sum_factors += spf[n]
14 n //= spf[n]
15 n = sum_factors
16 return n
17
18# Example usage
19print(smallestValue(15)) # Output: 5ℹ
Complexity note: The time complexity is O(n log log n) due to the Sieve of Eratosthenes, which efficiently computes the smallest prime factors. The space complexity is O(n) for storing the smallest prime factors.
- 1The process of replacing n with the sum of its prime factors will always lead to a prime number eventually.
- 2Using a sieve to precompute prime factors allows for efficient factorization.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.