c204 - 13194 - DPA Numbers II
題目描述
題目要求判斷給定的數字是 perfect number, deficient number 還是 abundant number。Perfect number 等於其所有真因數的和，deficient number 的真因數和小于自身，abundant number 的真因數和大于自身。
解題思路
程式首先預先計算一定範圍內的質數，並將其儲存在陣列 a 中。然後，對於每個輸入的數字 n，程式計算其所有真因數的和。如果和等於 n，則輸出 "perfect"；如果和小于 n，則輸出 "deficient"；如果和大于 n，則輸出 "abundant"。程式使用迴圈迭代來尋找質數，並使用另一個迴圈來計算每個數字的真因數和。
複雜度分析
- 時間複雜度: O(N * sqrt(N))，其中 N 是輸入數字的最大值。預計算質數的部分是 O(sqrt(N))，而計算每個數字的因數和的部分也是 O(sqrt(N))。
- 空間複雜度: O(sqrt(N))，用於儲存質數陣列。
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int a[78498];
int k=1;
bool c=true;
a[0]=2;
//------------------------------------
for(int i=3;i<=9999983;i+=2){
for(int j=3;j<=sqrt(i);j+=2){
if(i%j==0){
c=false;
break;
}
}
if(c==true){
a[k]=i;
k++;
}
}
//------------------------------------建表
int t=0,q=0,p=1;
while(cin >> t){
for(int i=1;i<=t;i++){
cin >> q;
for(int j=0;q<=a[j];j++){
if(q%a[j]==0){
p+=q;
p+=q/a[j];
}
}
}
}
}