Prime Factorization

题目:

Prime factorize a given integer.

e.g.
Given 10, return [2, 5].
Given 660, return [2, 2, 3, 5, 11].

分析:

这道题目并不需要提前知道谁是prime,很有意思

退出循环的条件必须是i * i <= num,其中==这样的case用来做9,25这样的数字

解法:

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

results matching ""

    No results matching ""