[Go] Maybe it's not fast, but easy to understand


  • 0

    First create a prime array, then divide n by primes to 1, or you can merge them

    func minSteps(n int) int {
    	if n == 1 {
    		return 0
    	}
    
    	retSteps := 0
    	arrPrime := makePrimer()
    	it := 2
    	for it < 1000 {
    		for arrPrime[it] == false { // find next prime number
    			it++
    		}
    
    		for n%it == 0 && n != it {
    			retSteps += it
    			n = n / it
    		}
    		if it == n {
    			retSteps += it
    			break
    		}
    		it++
    	}
    	return retSteps
    }
    
    func makePrimer() []bool {
    	MAX := 1000
    	arrPrime := make([]bool, 1000)
    	arrPrime[0] = false
    	arrPrime[1] = false
    	arrPrime[2] = true //0,1都不是素数,所以为false,2是素数,所以为true
    
    	for i := 2; i < MAX; i++ {
    		arrPrime[i] = true
    	}
    	for i := 2; i < MAX; i++ {
    		if arrPrime[i] == true {
    			for j := 2; j < MAX; j++ {
    				if j%i == 0 && j != i {
    					arrPrime[j] = false
    				}
    			}
    		}
    	}
    
    	return arrPrime
    }
    

Log in to reply
 

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