C++ 完全數的判斷（證明完全平方數不可能是完全數）

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)\)有：

\[sum(n) < n(n+1)/2 - n = (n^2-n)/2 \]

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;
}