a740 - 质因数之和
題目描述
題目要求計算一個正整數的所有質因數之和。例如，對於數字 6 (2 x 3)，輸出為 2 + 3 = 5；對於數字 8 (2 x 2 x 2)，輸出為 2 + 2 + 2 = 6。輸入為多個正整數，每行一個，直到 EOF 為止。
解題思路
程式碼首先預先計算並儲存一定範圍內的質數。然後，對於輸入的每個數字，程式碼迭代這些質數，嘗試將輸入數字分解成質因數。如果一個質數可以整除輸入數字，則將該質數加到總和中，並從輸入數字中除以該質數，直到該質數不能再整除輸入數字。最後，如果輸入數字大於 1，則剩餘的數字本身就是一個質因數，也需要加到總和中。
複雜度分析
- 時間複雜度: O(N * sqrt(M))，其中 N 是質數列表的長度，M 是輸入數字的大小。預先計算質數的時間複雜度是 O(sqrt(4800))，分解質因數的時間複雜度是 O(sqrt(M))。
- 空間複雜度: O(sqrt(4800))，用於儲存質數列表。
程式碼
#include<iostream>
int main()
{
std::cin.tie(0);
std::cin.sync_with_stdio(false);
int data[4800];
int i,j,k=1;
bool n=0;
data[0]=2;
for(i=3;i<4800;i+=2){
n=0;
for(j=0;j<k;j++){
if(i%data[j]==0){
n=1;
break;
}
}
if(n!=1){
data[k]=i;
k++;
}
}
long long int x,sum;
while(std::cin>>x){
sum=0;
for(j=0;j<k;j++){
if(x<=1)
break;
while(x%data[j]==0){
x/=data[j];
sum+=data[j];
}
}
if(x>1)
sum+=x;
std::cout<<sum<<"\n";
}
return 0;
}