c088 - 00516 - Prime Land
題目描述
題目要求將輸入的整數減一，並以質因數分解的形式輸出結果。輸入的整數以質因數分解的形式給定，例如 2 4 代表 2 的 4 次方。
解題思路
首先，需要預先計算一定範圍內的質數，例如到 5793。然後，讀取輸入的質因數分解，計算出原始數字。接著，將原始數字減一，並對減一後的數字進行質因數分解。最後，按照質因數和其對應的指數的順序輸出分解結果。質因數分解使用貪心算法，從最小的質數開始嘗試除，直到無法整除為止。
複雜度分析
- 時間複雜度: O(N * sqrt(X))，其中 N 是質數的數量，X 是輸入數字的大小。預先計算質數的時間複雜度為 O(sqrt(5793))，質因數分解的時間複雜度為 O(sqrt(X))。
- 空間複雜度: O(sqrt(X))，主要用於儲存質數列表和質因數分解的結果。
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int c,b[761];
string input;
bool a[5793]={1,1};
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=2;i<=77;++i)
for(int j=i+i;j<=5793;j+=i)
a[j]=1;
for(int i=0;i<5793;++i)
if(a[i]==0)
b[c++]=i;
while(getline(cin,input)){
if(input=="0")break;
input+=' ';
int tmp=0,ans=1,buf=0;
for(int i=0;i<input.length();++i){
while(input[i]>='0'&&input[i]<='9'){
buf*=10;
buf+=input[i]-'0';
++i;
}
if(tmp){
ans*=pow(tmp,buf);
tmp=buf=0;
}
else{
tmp=buf;
buf=0;
}
}
int it=0,ait=0;
--ans;
int rt[1001]={0};
while(it<760&&ans!=1){
while(ans%b[it]==0){
++buf;
ans/=b[it];
}
if(buf){
rt[ait++]=b[it];
rt[ait++]=buf;
buf=0;
}
++it;
}
if(ans!=1){
rt[ait++]=ans;
rt[ait++]=1;
}
for(int i=ait;i>0;i-=2){
cout << rt[i-2] << " " << rt[i-1] << " ";
}
cout << '\n';
}
}