Java 實現質因數分解算法：從邏輯分析到代碼實現

質因數分解邏輯

1. 從最小質數 2 開始嘗試除以 n。
2. 若能整除，輸出該質因子，n 更新為商，繼續嘗試同一因子。
3. 若不能整除，因子 +1 繼續。
4. 直到因子 > n 結束。

完整代碼

import java.util.Scanner;

public class PrimeFactorization {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("輸入正整數: ");
        int n = sc.nextInt();
        int k = 2;
        System.out.print(n + "=");
        while (k <= n) {
            if (k == n) {
                System.out.print(n);
                break;
            } else if (n % k == 0) {
                System.out.print(k + "*");
                n /= k;
            } else {
                k++;
            }
        }
    }
}

優化方向

• 因子只需遍歷到 sqrt(n)，剩餘 n > 1 即為最後一個質因子。
• 預計算質數表（埃氏篩）加速大數分解。
• 使用 BigInteger 支持超長整數。