质因数（素因数）分解（Java实现）
算术基本定理（唯一分解定理）
每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。
代码实现（Java）
import java.util.ArrayList;import java.util.List;/*** 求素数，素因式分解*/public class PrimeTest {/*** 求素数* 只需要判断3到√n的数* 步长为2，除了2以外，不存在是偶数的质数* n=√n*√n,n的因数除了√n，其他都是成对存在的，且必定一个大于√n一个小于√n* 假设n不是质数，且有个因数大于√n（不是n本身），则n必定有一个与之对应的小于√n的因数* 除了2以外，不存在是偶数的质数，所以在设计循环时可以设置步数step为2** @param n 数的范围* @return 素数列表*/public static List<Integer> getPrimes(int n) {List<Integer> primes = null;int m;if (n >= 2) {primes = new ArrayList<>();primes.add(2); // 2 是质数for (int i = 3; i <= n; i += 2) {// 遍历[3,n]的每个数for (m = 3; m < i; m += 2) {if (i % m == 0 || m * m > i) {// 如果找到因子则停止，此时数字i的因子为mbreak; // m 超过 √i 则停止，没有找到小于√i 的因子，则也没有必要找大于√i 的因子}}if (m * m > i) {// 如果 m 超过 √i ，将数字i本身加入列表primes.add(i);}}}return primes;}/*** 素因式分解* @param n 数的范围* @return 分解的素因式列表*/public static List<Integer> getPrimeFactors(int n) {List<Integer> primeFactors = new ArrayList<>();for (Integer i : getPrimes(n)) {while (n % i == 0) {n /= i;primeFactors.add(i);}}return primeFactors;}public static void main(String[] args) {System.out.println("35："+getPrimeFactors(35));System.out.println("100："+getPrimeFactors(100));System.out.println("120："+getPrimeFactors(120));}}
