Smallest Value After Replacing With Sum of Prime Factors - Problem

You are given a positive integer n.

Continuously replace n with the sum of its prime factors.

Note: 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.

Input & Output

Example 1 — Basic Composite Number

$ Input: n = 15

› Output: 5

💡 Note: 15 = 3 × 5, sum = 8. Then 8 = 2³, sum = 6. Then 6 = 2 × 3, sum = 5. Since 5 is prime, return 5.

Example 2 — Already Prime

$ Input: n = 3

› Output: 3

💡 Note: 3 is already prime, so it cannot be reduced further. Return 3.

Example 3 — Power of Prime

$ Input: n = 8

› Output: 5

💡 Note: 8 = 2³, sum = 2+2+2 = 6. Then 6 = 2×3, sum = 2+3 = 5. Since 5 is prime, return 5.

Constraints

2 ≤ n ≤ 1000

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12

The key insight is that we repeatedly replace n with the sum of its prime factors until reaching a prime number (which cannot be reduced further) or a cycle. The optimal approach checks if n is prime before factorization to save computation. Time: O(k × √n), Space: O(1).

Common Approaches

✓ Brute Force Simulation

⏱️ Time: O(k × √n) Space: O(1)

For each iteration, find all prime factors of n by trial division, sum them up, and replace n. Continue until n becomes stable (doesn't change).

Optimized with Early Prime Check

⏱️ Time: O(k × √n) Space: O(1)

Before factorizing each number, check if it's already prime. If so, return immediately since prime numbers cannot be reduced further. This saves computation time.

Brute Force Simulation — Algorithm Steps

Step 1: Find all prime factors of current n
Step 2: Sum all prime factors
Step 3: Replace n with the sum
Step 4: Repeat until n stops changing

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Value

Start with n = 15

First Iteration

15 = 3 × 5, sum = 3 + 5 = 8

Second Iteration

8 = 2³, sum = 2 + 2 + 2 = 6

Third Iteration

6 = 2 × 3, sum = 2 + 3 = 5

Final Result

5 is prime, cannot reduce further

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

int getPrimeFactorSum(int num) {
    int factorsSum = 0;
    int d = 2;
    while (d * d <= num) {
        while (num % d == 0) {
            factorsSum += d;
            num /= d;
        }
        d++;
    }
    if (num > 1) {
        factorsSum += num;
    }
    return factorsSum;
}

int solution(int n) {
    while (1) {
        if (isPrime(n)) {
            return n;
        }
        
        int primeSum = getPrimeFactorSum(n);
        if (primeSum == n) {
            return n;
        }
        n = primeSum;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × √n)

k iterations of prime factorization, each taking O(√n) time

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Smallest Value After Replacing With Sum of Prime Factors - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler