b369 - [福州19中]因子和阶乘
題目描述
題目要求將給定的正整數 n 的階乘 (n!) 分解成質因數的乘積形式，並從小到大輸出每個質因數的指數。例如，如果 n=5，則 5! = 120 = 2^3 * 3^1 * 5^1，輸出應為 3 1 1。
解題思路
首先，使用埃拉托斯特尼篩法預先計算出小於 30000 的所有質數。然後，對於給定的輸入 k，遍歷從 2 到 k 的所有數字 i。對於每個 i，計算 i 的質因數分解，並將每個質因數的指數累加到一個臨時數組 tmp 中。最後，找到 tmp 數組中非零項的最大索引 mait，並輸出 tmp 數組中從索引 0 到 mait-1 的所有值，以空格分隔。
複雜度分析
- 時間複雜度: O(30000 * log(30000) + k * sqrt(k))。O(30000 * log(30000)) 是篩選質數的複雜度，O(k * sqrt(k)) 是計算每個數字的質因數分解的複雜度。
- 空間複雜度: O(30001)。主要用於儲存質數數組 p 和臨時數組 tmp。
程式碼
#include <iostream>
using namespace std;
int n,pr[4001],it,k;
bool p[30001]={1,1};
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=2;i<=174;++i)
for(int j=i+i;j<=30000;j+=i)
p[j]=1;
for(int i=0;i<=30000;++i)
if(p[i]==0)
pr[it++]=i;
while(cin >> k){
int tmp[30001]={0},mait=0;
for(int i=2;i<=k;++i){
n=i;
it=0;
while(n!=1){
while(n%pr[it]==0&&n!=1){
++tmp[it];
n/=pr[it];
}
++it;
}
mait=max(it,mait);
}
cout << k << "!=";
for(int i=0;i<mait;++i)
cout << tmp[i] << " ";
cout << "\n";
}
}