題目要求
- C++ 函數
- 輸入整數 k
- 輸出所有質因數，格式：`126=2*3*3*7` (含等號、星號分隔、無尾隨星號)
核心演算法：試除法 (優化至 √n)
#include
#include
#include
using namespace std;
/**
* 質因數分解並格式化輸出
* @param k 輸入正整數 (k >= 2)
*/
void primeFactorize(int k) {
if (k < 2) { cout << "輸入需 >= 2\n"; return; }
int original = k;
vector factors;
// 1. 處理因子 2
while (k % 2 == 0) {
factors.push_back(2);
k /= 2;
}
// 2. 處理奇數因子 3, 5, 7... 至 sqrt(k)
for (int i = 3; i <= sqrt(k); i += 2) {
while (k % i == 0) {
factors.push_back(i);
k /= i;
}
}
// 3. 剩餘 k > 1 即為質數
if (k > 1) factors.push_back(k);
// 4. 格式化輸出
cout << original << "=";
for (size_t i = 0; i < factors.size(); ++i) {
if (i > 0) cout << "*";
cout << factors[i];
}
cout << endl;
}
int main() {
int x;
cout << "輸入整數: ";
cin >> x;
primeFactorize(x);
return 0;
}
執行範例
輸入整數: 126
126=2*3*3*7
輸入整數: 13
13=13
輸入整數: 100
100=2*2*5*5
輸入整數: 1
輸入需 >= 2
關鍵細節解析
| 細節 | 處理方式 |
|---|
| 重複質因數 | `while (k % i == 0)` 迴圈持續除以同一因子，收集所有重複項 |
| 輸出格式 | 先印 `原數=`，迴圈中 `i>0` 才印 `*`，**無尾隨星號** |
| 效能優化 | 先除 2，再 `i+=2` 只試奇數，上限 `sqrt(k)` 動態縮減 |
| 大質數殘餘 | 迴圈結束後 `k>1` 代表剩餘大質數 (如 126→7)，直接收集 |
| 邊界 k=1 | 質因數分解定義域為 >=2，輸入 1 給予提示 |
進階：超大整數 (64-bit / BigInteger)
// 64-bit 版 (long long)
void primeFactorizeLL(long long k) {
// 邏輯相同，i 為 long long，sqrt 用 sqrtl
// 注意：超過 10^12 試除法極慢，需 Pollard's Rho
}
// C++ 無內建 BigInteger，可用 boost::multiprecision::cpp_int
#include
using boost::multiprecision::cpp_int;
// 實作較複雜，教學通常不要求
常見錯誤修正 (針對原圖片程式碼)
| 原程式碼問題 | 修正 |
|---|
| `#include"iostream"` 引號 | `#include ` 標準庫用尖括號 |
| `void main()` | `int main()` 標準簽名 |
| `j=(int)sqrt((float)x)` 重複計算 sqrt | 動態 `i*i <= k` 或 `i <= sqrt(k)` 並在迴圈內更新 |
| 輸出格式無等號、有尾隨星號 | 參考上方格式化邏輯 |
總結
質因數分解核心：**試除法 + 動態縮減上限 + 收集重複因子 + 格式化輸出**。C++ 使用 `vector` 收集因子、迴圈輸出控制星號，**確保格式完全符合 `n=p1*p2*...`**。教學環境 `int` 範圍 (2~21億) 試除法足夠；超大數需 Pollard's Rho + Miller-Rabin。
