Prime Factorization

Prime Factorization

Prime factorize a given integer.

Example

Given 10, return [2, 5].

Given 660, return [2, 2, 3, 5, 11].

Note

You should sort the factors in ascending order.

思路：
i从2开始到√ num。如果能除尽i，把i加到结果里，并把num变成num / i接着试。除不尽了就把i加1接着试。最后循环出来以后看一下剩下的num如果不等于1，说明还没除完。还有最后一个大于√ num的质因数要加到结果里。

public class Solution {
    /**
     * @param num an integer
     * @return an integer array
     */
    public List<Integer> primeFactorization(int num) {
        // Write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        
        for (int i = 2; i * i <= num; i++) {
            while (num % i == 0) {
                result.add(i);
                num /= i;
            }
        }
        
        if (num != 1) {
            result.add(num);
        }
        
        return result;
        
    }
}