Prime Factorization(lintcode 235)*

Description

Prime factorize a given integer.

Notice:
You should sort the factors in ascending order.

Example

Given 10, return [2, 5].

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

Interface

public class Solution {
    /**
     * @param num an integer
     * @return an integer array
     */
    public List<Integer> primeFactorization(int num) {
        // Write your code here
    }
}

Idea

The loop condition i * i <= num can make the running time much shorter.

Solution

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