整数因子分解
复杂度为(O(sqrt(n)))的方法，从1逐个数字判断即可，如果能够整除该数(i)，将(i)与(n/i)同时加入分解结果列表中去。需要注意去重，也就是避免(i==n/i)这种情况。java代码如下：
public List<Integer> factorDecode(int n) {
List<Integer> list = new ArrayList<>();
for(int i = 1; i * i <= n; i++) {
if(n % i == 0) {
if(i * i != n) {
list.add(i);
list.add(n/i);
}
else list.add(i);
}
}
return list;
}
整数的质因子分解
整数的质因子分解是指，对于任何大于等于2的正整数(n),都有以下公式成立：
[n = prod_{i=1}^kp_i, p_i是素数
]
也就是需要将n分解成质因数的连乘积。因为这样的分解一定存在，并且如果将这些质因数从小到大排列，那么这样的分解就是唯一的。假设上面的(p_i)已经排过序了，那么我们稍微改写一下公式，就能得到朴素的解法。
[n/p1 = prod_{i=2}^kp_i,pi是素数
]
显然这是一个递归定义的过程，可以使用递归解法，也可以使用迭代解法，下面给出迭代解法的java代码:
public List<Integer> primeFactorDecode(int n) {
int i = 2;
List<Integer> ans = new ArrayList<>();
while(n > 1) {
while(n % i == 0) {
ans.add(i);
n /= i;
}
i++;
}
return ans;
}
基于以上两种分解的一些变形题目
基于上面的两种整数分解方法，一些题目会在此基础稍微变形，但本质上还是进行这两种分解。比如，有的题目给出一个定义，定义n因子数，如4因子数，也就是当一个整数恰好有4个因子时，就是一个4因子数，给定一个数组，求出数组中有多少个这样的4因子数。直接按照定义遍历即可。