Java Solution--Summation of prime dividers


  • 0
    W

    This problem is the same as calculate the sum of the prime dividers. First, if n is prime, e.g. 5, then we need one copy and 4 paste, thus, the result is 1+4=5.

    Now, say n=2x5x5x7, we can first use two steps to get 2A, then treat "2A" as a whole to get 5 "2A"s, that is "10A". Then, we treat "10A" as whole to get 5 "10A"s, that is "50A"s. Similarly, we still need 7 steps( 1 copy and 6 pastes) to get 7 "50A"s. Thus, we have 2+5+5+7=19 steps to obtain "350A"s for n=350=2x5x5x7. The following is the corresponding codes.

        public int minSteps(int n) {
            int res=0;
            for(int i=2;;){
                if(n%i==0){
                    res+=i;
                    n/=i;
                }
                else i++;
                if(n<i) break;
            }
            return res;
        }
    

  • 0
    W

    Sorry, a wrong usage of English word, it should be prime factors.


Log in to reply
 

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