# java solution with explanation

• I listed the answers to the first 8,
input: 1 2 3 4 5 6 7 8
output: 0 2 3 4 5 5 7 6

1,I found, If the input is a prime number, then the result is itself.

2,Non prime，find its The largest multiple and the prime number,and then find the Maximum multiple;

forExample:input:18 output 8; int result = 0;
18 is non prime, The largest multiple and the prime number 3 , the Maximum multiple is 9
result += 18 / 9; and then find the Maximum multiple of 9; is 3 so result += 9/3; when (the Maximum multiple) = (The largest multiple and the prime number ) break the loop;

and result + The largest multiple and the prime number 3 ,so result = 2 + 3 + 3 = 8;

``````public int minSteps(int n) {
if(n==1)return 0;
if(zhiShu(n))return n;
for(int i=n/2; i>=2; i--){
if(zhiShu(i) && n%i==0){
int res = 0;
int tmp = n;
while((tmp=zuiDaBeiShu(tmp))!=-1){
res += n/tmp;
n = tmp;
if(tmp==i){
break;
}
}

return i+res;
}
}
return -1;
}

// Is it a prime number?
public boolean zhiShu(int n){
for(int i=2; i<=Math.sqrt(n); i++){
if(n%i==0){
return false;
}
}
return true;
}
// find Maximum multiple
public int zuiDaBeiShu(int n){
for(int i=n/2; i>=2; i--){
if(n%i==0){
return i;
}
}
return -1;
}``````

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