PrimeFactorization

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.

Analysis:

这道题是遍历问题，给出一个num，让它从从最小的factor开始遍历

• 如果可以整除，则把factor加到list中同时num = num / factor; 下一次继续看能否整除这个factor。
• 如果不能整除，则factor++。
• 只要遍历到num = 1，或者factor = sqrt（num）即可跳出循环。此时，如果num！=1，则证明还有一个大于sqrt（num）的prime number存在，此时再向list中加入一个num即可。

这道题在于不用求prime number，因为如果它将从2开始的数都除到不能再除，则每一次它再能整除的数都只能是prime number。

code

public class Solution {
    /**
     * @param num an integer
     * @return an integer array
     */
    public List<Integer> primeFactorization(int num) {
        // Write your code here
        List<Integer> list = new ArrayList<Integer>();
            int fac = 2;
            int number = num;

            while (number != 1 && fac < (int) (1 + Math.sqrt(num))) {
                if (number % fac == 0) {
                    number /= fac;
                    list.add(fac);
                } else {
                    fac++;
                }
            }
        if (number != 1) {
            list.add(number);
            return list;
        }
        return list;
    }
}