Smallest Value After Replacing With Sum of Prime Factors

Medium
699.

Smallest Value After Replacing With Sum of Prime Factors

Smallest Value After Replacing With Sum of Prime Factors is a medium coding problem on math, simulation and number theory, asked in Amazon, Adobe and Samsung interviews.

Repeatedly replace n with the sum of its prime factors counted with multiplicity — so 12 = 2 × 2 × 3 becomes 7.

Return the value n settles on, which is the smallest value it ever reaches.

Example 1

Input
n = 15
Output
5
Explanation
15 becomes 3 + 5 = 8, then 2 + 2 + 2 = 6, then 2 + 3 = 5, and 5 is prime.

Example 2

Input
n = 3
Output
3
Explanation
A prime is its own sum of prime factors.

Example 3

Input
n = 12
Output
7
Explanation
12 becomes 2 + 2 + 3 = 7.

Constraints

  • 2 <= n <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var smallestValue = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Smallest Value After Replacing With Sum of Prime Factors Solution

Smallest Value After Replacing With Sum of Prime Factors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Smallest Value After Replacing With Sum of Prime Factors is a medium coding problem on math, simulation and number theory, asked in Amazon, Adobe and Samsung interviews.

Problem statement

Repeatedly replace n with the sum of its prime factors counted with multiplicity — so 12 = 2 × 2 × 3 becomes 7.

Return the value n settles on, which is the smallest value it ever reaches.

Example 1

Input: n = 15
Output: 5
Explanation: 15 becomes 3 + 5 = 8, then 2 + 2 + 2 = 6, then 2 + 3 = 5, and 5 is prime.

Example 2

Input: n = 3
Output: 3
Explanation: A prime is its own sum of prime factors.

Example 3

Input: n = 12
Output: 7
Explanation: 12 becomes 2 + 2 + 3 = 7.

Constraints

  • 2 <= n <= 100000

Hints for Smallest Value After Replacing With Sum of Prime Factors

  1. Hint 1

    Factorise by trial division up to the square root; whatever is left over is itself prime.

  2. Hint 2

    Count each factor as many times as it divides — 4 contributes 2 + 2, not just 2.

  3. Hint 3

    The process stops exactly when n is prime, because a prime's factor sum is itself.

How to solve Smallest Value After Replacing With Sum of Prime Factors

Each round is a trial-division factorisation whose factors are summed with multiplicity. The sequence strictly decreases until it hits a prime, which is a fixed point.

Approach

  1. Write a helper that factorises x by trial division from 2 up to sqrt(x), adding each prime as many times as it divides, and adding the leftover if it exceeds 1.
  2. Loop: compute the helper's value; if it equals the current value, return it; otherwise continue from it.

Why it works

For composite x = a · b with a, b >= 2, the sum of prime factors is at most a + b <= a · b, with equality only at 4 — and 4 maps to 4, so the loop terminates there too. For a prime p the sum is p itself, so primes are the fixed points and the sequence never increases.

Complexity

  • Time — O(log n · sqrt(n)) overall — the value shrinks fast
  • Space — O(1)

Pitfalls

  • Summing distinct primes rather than counting multiplicity gives 5 for 12 instead of 7.
  • Forgetting the leftover factor after the loop loses the largest prime whenever it exceeds sqrt(x).
  • 4 is a fixed point and would loop forever without the 'stop when unchanged' test.

Reference solution

Python

def smallestValue(n: int) -> int:
    def prime_sum(v: int) -> int:
        total = 0
        x = v
        p = 2
        while p * p <= x:
            while x % p == 0:
                total += p
                x //= p
            p += 1
        if x > 1:
            total += x
        return total

    cur = n
    while True:
        nxt = prime_sum(cur)
        if nxt == cur:
            return cur
        cur = nxt

Java

public static int smallestValue(int n) {
    int cur = n;
    while (true) {
        int next = primeSumOf(cur);
        if (next == cur) return cur;
        cur = next;
    }
}

static int primeSumOf(int v) {
    int total = 0, x = v;
    for (int p = 2; (long) p * p <= x; p++) {
        while (x % p == 0) { total += p; x /= p; }
    }
    if (x > 1) total += x;
    return total;
}

C++

static int primeSumOf(int v) {
    int total = 0, x = v;
    for (int p = 2; (long long) p * p <= x; p++) {
        while (x % p == 0) { total += p; x /= p; }
    }
    if (x > 1) total += x;
    return total;
}

int smallestValue(int n) {
    int cur = n;
    while (true) {
        int next = primeSumOf(cur);
        if (next == cur) return cur;
        cur = next;
    }
}

JavaScript

var smallestValue = function(n) {
    var primeSum = function(v) {
        var total = 0, x = v;
        for (var p = 2; p * p <= x; p++) {
            while (x % p === 0) { total += p; x = x / p; }
        }
        if (x > 1) total += x;
        return total;
    };
    var cur = n;
    for (;;) {
        var next = primeSum(cur);
        if (next === cur) return cur;
        cur = next;
    }
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue