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