题目的主要信息：

完全数所有的真因子（即除了自身以外的约数，包括1）的和，恰好等于它本身
请输出n以内的完全数的个数
$1 < = n < = 5 * 1 0^{5}$

方法一：枚举

具体做法：

我们可以枚举1到n的每个数字，判断其是否是完全数，如果是则计数，否则跳过。

判断的时候我们从1遍历到 $\sqrt n$ 找每个数的因子，如果是因子我们将这个因子和这个因子对应的另一个相加，当然要判断因子是否是 $n$ 的开方，如果刚好是开方就只加一次。然后减去这个数本身，因为因子为1时另一个因子为这个数，累加和加上了这个因子本身，最后检查这个累加和与这个数是否相等，相等则是完全数，不相等则不是。

alt

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

bool isPefect(int n){ //判断数字n是否是完全数
    int sum = 0;
    for(int i = 1; i * i <= n; i++){ //遍历从1到根号n
        if(n % i == 0){ //如果是因子
            if(i * i == n){ //先判断是否是开方，开方只有1个因子
                sum += i; 
                break;
            }
            else //其他情况都有两个因子
                sum += i + n / i;
        }
    }
    sum -= n; //减去本身
    return sum == n ? true : false; //判断和是否等于本身
}
int main(){
    int n;
    while(cin >> n){
        int count = 0;
        for(int i = 1; i <= n; i++){ //枚举数字1到n
            if(isPefect(i)){ 
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O(n* \sqrt n)$ ，遍历1到n，每个数检查从1到 $\sqrt n$
空间复杂度： $O (1)$ ，无额外空间

方法二：打表

具体做法：

从方法一的答案中我们发现，完全数的个数是非常少的， $5 * 1 0^{5}$ 范围内就只有6，28，496，8192四个，而下一个完全数已经达33550336，超出输入范围。因此我们可以判断输入的n在上面哪个范围之内，根据范围输出相应的完全数个数。

alt

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        //根据n所属区间输出
        if(n < 6)
            cout << 0 << endl;
        else if(n < 28)
            cout << 1 << endl;
        else if(n < 496)
            cout << 2 << endl;
        else if(n < 8192)
            cout << 3 << endl;
        else
            cout << 4 << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (1)$ ，直接判断，常数时间
空间复杂度： $O (1)$ ，无额外空间

题解 | #完全数计算#

题目的主要信息：

方法一：枚举

方法二：打表