d131 - 00160 - Factors and Factorials
題目描述
題目要求計算 N! 的質因數分解，並以特定格式輸出每個質因數及其出現次數。輸出格式要求每行最多顯示 15 個質因數，超過則換行。
解題思路
程式首先讀取輸入的 N 值。然後，對於從 2 到 N 的每個數字 i，進行質因數分解，並將每個質因數的出現次數記錄在 ans 陣列中。ans 陣列的索引代表質因數，值代表其出現次數。最後，程式遍歷 ans 陣列，輸出每個質因數及其出現次數，並按照題目要求的格式進行排版。
複雜度分析
- 時間複雜度: O(N * sqrt(N))。外層迴圈從 2 到 N 迭代，內層迴圈進行質因數分解，最壞情況下需要迭代到 sqrt(i)。
- 空間複雜度: O(101)。
ans陣列的大小固定為 101，因此空間複雜度為常數。
程式碼
#include <iostream>
#include <iomanip>
using namespace std;
int main(){
int k;
while(cin >> k){
if(k==0)break;
cout << k << "! = ";
int ans[101]={0},ma=0,col=0;
for(int i=2;i<=k;++i){
int tmp=i;
for(int j=2;tmp!=1;++j){
while(tmp%j==0){
++ans[j];
tmp/=j;
ma=max(j,ma);
}
}
}
for(int i=0;i<=ma;++i){
if(ans[i]){
cout << setw(2) <<ans[i] << " ";
++col;
if(col%15==0){
cout << "\n";
}
}
}
cout << "\n";
}
}