e929 - pC. 分解質因數
題目描述
題目要求將輸入的正整數 N 分解成質因數，並以指定格式輸出。質因數需由小到大排列，相同質因數則以次方形式表示。
解題思路
此題的核心是質因數分解。程式從 2 開始迭代到輸入數字的平方根。對於每個數字 i，判斷 i 是否為 n 的因數。如果是，則計算 i 能夠被 n 整除的次數，並將結果以 i^次數 的形式輸出。迭代完畢後，如果 n 仍然大於 1，則表示 n 本身是一個質因數，將其輸出。使用平方根優化可以減少迭代次數，提高效率。
複雜度分析
- 時間複雜度: O(sqrt(n))
- 空間複雜度: O(1)
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int n;
cin >> n;
cout << n << " = ";
bool start=0;
int s=sqrt(n);
for(int i=2;i<=s;++i){
int tt=0;
while(n%i==0){
++tt;
n/=i;
}
if(tt>1){
if(start)cout << "* ";
cout << i << "^" << tt << " ";
start=1;
}
else if(tt){
if(start)cout << "* ";
cout << i << " ";
start=1;
}
}
if(n!=1){
if(start)cout << "* ";
cout << n;
}
}