Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2507.html

2507. Smallest Value After Replacing With Sum of Prime Factors

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

  • 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;
            }
        }
    }
    
  • 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;
            }
        }
    };
    
  • 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
    
    
  • 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
    	}
    }
    

All Problems

All Solutions