Prime Factor Sum Descent

Medium

You are given an integer n. The following step is applied over and over: factor the number into primes and replace it with the sum of those primes. A prime that divides the number several times is counted that many times (for example, 12 = 2·2·3 becomes 7). Return the smallest value the number ever takes during the process, the starting value included.

Example 1

n=20 → 5

20 = 2·2·5 → 2+2+5 = 9; 9 = 3·3 → 6; 6 = 2·3 → 5; 5 is prime and maps to itself. The smallest value is 5.

Example 2

n=4 → 4

4 = 2·2 → 2+2 = 4, so the number never changes and the answer is 4.

Example 3

n=13 → 13

Constraints

2 ≤ n ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Number Theory Simulation

Similar problems

Fold the Digits Down to One Easy Top of a Digit Pyramid Easy Multiplying Digit Strings Medium Primes Below a Bound Medium Multiply Complex Numbers in Strings Medium

Input

n=20

Expected

Run checks the first 3 tests in your browser. Submit checks all 46 tests on the server, hidden ones included.