C++ 完全数的判断

对于自然数\(n\)，其除了自身以外的所有因数的和，等于其自身的，称\(n\)为完全数。在C++中可以通过遍历\(1\)到\(n\)找出所有因数，然后求和验证。但\(n\)次遍历往往无法满足时间复杂度的要求。

注意到，对自然数\(n\)，假设其存在因数\(a\)，则必存在因数\(b = n / a\)，且\(min(a, b)\)不大于\(\sqrt(n)\)。利用这条性质可以将原本需要的n次遍历减少为\(\sqrt(n)\)次遍历。

int n, sum = 1;

cin >> n; // n为输入的自然数n

for (int i = 2; i <= n / i; i ++ ){

if (n % i == 0){

sum += (i + n / i);

}

}

一般的代码中都没有考虑\(i = n / i\)的情况，即\(n\)为完全平方数的情况。如何证明完全平方数不可能是完全数？

证明：完全平方数不可能是完全数

对大于3的正整数\(n\)，其除了自身的约数的和\(sum(n)\)有：

对于一个完全平方数$ k = n * n \(，如果其为完全数，则\) n \(的约数和\)sum(n) = k - n = n^2 - n$，显然不可能。所以完全平方数不需要特别处理。

C++ 程序

#include <iostream>
#include <cmath>
using namespace std;

int main(){
int n;
cin >> n;

while(n--){
int x, sum = 1;
cin >> x;
for (int i = 2; i < sqrt(x); i ++){
if (x % i == 0){
sum += i;
sum += x / i;
}
}

if (x != sum || x == 1)
printf("%d is not perfect\n", x);
else
printf("%d is perfect\n", x);
}

return 0;
}