c666 - 質數乘積
題目描述
題目要求計算前 n 個質數的乘積。給定一個整數 n，程式需要輸出前 n 個質數相乘的結果。
解題思路
此題的核心在於高效地計算質數並進行大數乘法。程式首先使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 預先計算出前 5000 個質數，並將其儲存在 prime 陣列中。然後，程式使用一個 ans 陣列來儲存前 i 個質數的乘積，透過迭代地將前一個乘積與當前質數相乘來計算。由於質數乘積可能非常大，程式使用字串 (string) 來儲存和處理這些大數。mult 函數實現了大數乘法的邏輯，它將一個字串表示的數字乘以一個整數，並返回結果字串。最後，程式讀取輸入的 n，並輸出 ans[n-1]，即前 n 個質數的乘積。
複雜度分析
- 時間複雜度: O(N^2 + M * L)，其中 N 是篩選質數的上限 (約為 48620)，M 是輸入 n 的最大值 (5000)，L 是大數乘法的平均長度。埃拉托斯特尼篩法的時間複雜度為 O(N log log N)，近似為 O(N^2)。大數乘法
mult的時間複雜度為 O(L^2)，由於需要進行 M 次乘法，因此總時間複雜度為 O(M * L^2)。 - 空間複雜度: O(M + N)，其中 M 是
ans陣列的大小 (5001)，N 是篩選質數所需的空間 (約為 48621)。
程式碼
#include <iostream>
using namespace std;
int it=0;
string ans[5001]={"2"};
int prime[5001];
string mult(string x,int y){
int tmp[21001]={0};
int xl=x.length(),it=0;
string rt;
while(y){
int t=y%10;
for(int i=0;i<xl;++i)
tmp[it+i]+=(x[xl-1-i]-48)*t;
y/=10;
++it;
}
for(int i=0;i<21001;++i)
if(tmp[i]>=10){
tmp[i+1]+=tmp[i]/10;
tmp[i]%=10;
}
for(int i=21000;i>=0;--i)
if(tmp[i]!=0){
it=i;
break;
}
for(int i=it;i>=0;--i)
rt+=tmp[i]+'0';
return rt;
}
bool p[50001]={1,1};
int main(){
cin.tie(0);ios::sync_with_stdio(false);
for(int i=2;i<=221;++i)
for(int j=i+i;j<=48620;j+=i)
p[j]=1;
for(int i=0;i<=48620&&it<=5000;++i)
if(p[i]==0)
prime[it++]=i;
for(int i=1;i<=5000;++i)
ans[i]=mult(ans[i-1],prime[i]);
while(cin >> it)
cout << ans[it-1] << "\n";
}