HDOJ 1405 The Last Practice：質因數分解輸出格式詳解（Java）

題目：對輸入正整數 n (1 < n < 65536) 進行質因數分解，按質因子升序輸出 質因子 指數 對，遇負數結束。輸出格式嚴格要求：每行末尾有空格，Case 間空行，Case k. 含點號。

算法邏輯

1. 從 2 試除到 sqrt(n)。
2. 計算每個質因子指數 cnt，n /= i 循環除盡。
3. 若最後 n > 1，說明剩餘一個大於 sqrt(original_n) 的質因子，指數為 1。

Java 代碼（嚴格遵循格式）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = 0;
        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n < 0) return;
            if (tc > 0) System.out.println(); // Case間空行
            System.out.println("Case " + (++tc) + ".");
            for (int i = 2; i <= Math.sqrt(n); i++) {
                int cnt = 0;
                while (n % i == 0) { n /= i; cnt++; }
                if (cnt > 0) System.out.print(i + " " + cnt + " "); // 行末必須有空格
            }
            if (n > 1) System.out.print(n + " 1 "); // 剩餘質因子
            System.out.println(); // 換行
        }
    }
}

格式關鍵點

• Case 1. —— 數字後有點號。
• 每行輸出結尾 必須有一個空格（如 2 2 3 1 5 1 ）。
• Case 之間 有一個空行（首 Case 前無空行）。
• 質因子按升序輸出（試除法天然保證）。

樣例驗證

輸入:
60
12
-1

輸出:
Case 1.
2 2 3 1 5 1 

Case 2.
2 2 3 1