Skip to content

2507. Smallest Value After Replacing With Sum of Prime Factors

SourceWeekly Contest 324 Q2DifficultyMediumRating1499

Description

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

Solutions

Solution 1: Brute Force Simulation

Thinking

Replace \(n\) by the sum of its prime factors until the value stops changing. Direct simulation is fine for \(n\le 10^5\): the sum is strictly smaller on composites and equals \(n\) on primes, so the process terminates.

Trial-divide the current value and add the factors. If the sum equals the original, the fixed point is reached; otherwise continue. Each factorization is \(O(\sqrt{n})\) and few iterations occur.

According to the problem statement, we can perform a process of prime factorization, i.e., continuously decompose a number into its prime factors until it can no longer be decomposed. During the process, add the prime factors each time they are decomposed, and perform this recursively or iteratively.

The time complexity is \(O(\sqrt{n})\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func smallestValue(n int) int {
    for {
        t, s := n, 0
        for i := 2; i <= n/i; i++ {
            for n%i == 0 {
                s += i
                n /= i
            }
        }
        if n > 1 {
            s += n
        }
        if s == t {
            return s
        }
        n = s
    }
}

Comments