# Java math solution

• I think for this problem we just need to find all the prime factors for the number, then add them up.

``````public int minSteps(int n) {
if(n == 1) return 0;
if(n <= 5) return n;
int count = 0;
int a = 2;
while(a * a <= n) {
while(n % a == 0) {
count += a;
n /= a;
}
a++;
}
if(n > 1) count+= n;
return count;
}
``````

• public int minSteps(int n) {
if(n == 1) return 0;
if(n <= 5) return n;
int count = 0;
int a = 2;
while(a * a <= n) {
while(n % a == 0) {
count += a;
n /= a;
}
a++;
}
if(n > 1) count+= n;
return count;
}

Explanation :
To multiply the string by k times, the most naive way is to copy once and paste k-1 times. That takes k steps.

Notice how this becomes a multiplication problem : the operation can be treated as multiplying the existing string k times, and it takes k steps.

Going back to k. We don't need to take k steps to multiply the string k times, if k is not a prime number. Only when k is a prime number, we need to take at least k steps to achieve k multiplication, because there's no other way around to further divide the operation., otherwise, let's say k's not a prime number and its prime factors are x,x,y,y,z, i.e, k = x * x * y * y * z. Remember multiplication of x times means x steps (because x is a prime number). so to achieve k, we actually only need x+x+y+y+z steps.

QED.

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