This question is actually calculate the sum of prime divisors of n. Share my thought and fast Java Solution


  • 0
    T

    When n is a prime number 2,3,5... 19, the result has to be copy paste one by one and result in n operations. For any prime divisor of n, this is also true. So this question actually becomes calculate the sum of its prime divisors. Attach my code your reference.

        public int minSteps(int n) {
            Set<Integer> set = new HashSet<>();
            boolean[] notPrime = new boolean[n+1];
            for (int i = 2; i * i <= n; i++) {
                if (notPrime[i]) {
                    continue;
                }
                set.add(i);
                for (int j = i + i; j <= n; j+= i) {
                    notPrime[j] = true;
                }
            }
            return minSteps(n, set);
        }
        
        private int minSteps(int n, Set<Integer> set) {
            if (n == 0 || n == 1) {
                return 0;
            }
            Set<Integer> remove = new HashSet<>();
            for (int v : set) {
                if (n % v == 0) {
                    set.removeAll(remove); // for any non dividable prime, remove it
                    return v + minSteps(n/v, set);
                } else {
                    remove.add(v);
                }
            }
            return n;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.