java solution with explanation


  • 0
    L

    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;
    }

Log in to reply
 

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