分解质因数

1. 问题描述

编写一个程序，给定一个正整数n（n>=2），分解质因数，返回分解结果。

例如：

1. n=6，返回：[2,3]；
2. n=18，返回[2,3,3]；
3. n=3，返回[3]

2. 算法描述

准备一个答案列表ans，设置一个循环遍历i从2开始，循环条件是i<=n；对于每一个i：

1. 如果i==n，那么把i加入ans，返回；
2. 只要n%i==0，那么就把i加入ans；n/=i;
3. 如果n是质数，那么就把n加入ans，返回，否则i++

3. 代码

import java.util.*;

public class PrimeNumberDecomposition {
    
    public static List<Integer> decomposition(int n) {
        List<Integer> ans = new ArrayList<>();
        for(int i = 2; i <= n; ) {
            if(i == n) {
                ans.add(i);
                break;
            }
            while(n % i == 0) {
                ans.add(i);
                n /= i;
            }
            if(primeNum(n)) {
                ans.add(n);
                break;
            }
            ++i;
        }
        return ans;
    }
    
    private static boolean primeNum(int n) {
        if(n <= 3) return n != 1;
        if(n % 6 != 1 && n % 6 != 5) return false;
        for(int i = 5, limit = (int)Math.sqrt(n); i <= limit; i += 6) {
            if(n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Input your number please:");
        int num = sc.nextInt();
        do {
            System.out.println("Result is: " + decomposition(num));
            System.out.println("Input your number please:");
            num = sc.nextInt();
        }while(num != 1);
        System.out.println("Bye~~");
    }
}