My first post.

There are many good solutions. Here, I am trying to explain the idea behind them. (In my opinion, it is not very obvious, even you may write the code correctly.)

If N is a prime number, we have to copy A for N time.

Consider a composite number N, it can be decomposed as p1 * p2 *...pk.

Define F(N) as the number of steps. F(N) is F(N/p1) +p1 = F(N/p1p2) + p1 + p2 = F (1) + p1 + p2 + ... pk.

The problem is how to select these values to minimize F(N) under the constrain: p1 * p2 *...pk = N.

In high school, we knew p1 + p2 >= sqrt(p1 * p2); it is equal when p1 = p2. And the summation increases when the difference between p1 and p2 increases. The similar rule also applys for p1+p2+…pk. We need to make sure p1, p2…pk as close as possible.

But still we don’t know how many p we should use. For example, 36 = 6 * 6 = 2 * 18 = 2 * 3 * 2 * 3. Which we should use?

First, we should discard 2 * 18 because we need to make sure p1 and p2 as close as possible. But how to choose from 6 * 6 or 2 * 3 * 2 * 3.

We can use an easier example p1 * p2 = p1 * p3 * p4 = p1 * d * (p2/d) (Here p2 = p3 * p4 and d = p3, p2/d = p4, p2 > d = p3, p2 > p2/d = p4)

p2 >= d + p2/d because p2 * d >= d^2 + p2.

As a result, we also need to decompose the number N as much as possible.

So, each loop, we start from i = 2 to get the smallest possible candidate number. These numbers are also the closest number we could find.

I hope it is helpful. (I don't know how to submit a code with a better format, sorry about it).

'''

public int minSteps(int n) {

int res = 0;

for(int i=2;i<=n;i++){

while(n%i == 0){

res+= i;

n=n/i;

}

}

return res;

}

'''