题目的主要信息：

完全数是指除了它本身以外所有因子之和等于它本身的数。
要求输入n，输出n以内(含n)完全数的个数。

方法一：

遍历一遍n内的所有整数，用一个整数count来记录n内的完全数个数。首先计算每个整数num的所有因子，找因子的方法是枚举num内的所有整数，判断是否能被num整除，若能整除，则是num的因子。再计算它的真因子之和，与整数本身进行比较，若相同则表示这个整数是完全数，count加1。 alt

具体做法：

#include<iostream>
#include<vector>

using namespace std;
vector<int> fin_factors(int num){//找到num的所有的因子
    vector<int> factors;
    for(int i=1;i<=num;i++){
        if(num%i==0){//能够被num整除的就是num的因子
            factors.push_back(i);
        }
    }
    return factors;
}

bool isPerfect(vector<int>& factors,int num){//计算除num本身以外所有因子之和
    int sum=0;
    for(int i=0;i<factors.size();i++){
        if(factors[i]!=num){
            sum+=factors[i];
        }
    }
    if(sum==num){//真因子之和等于本身即为完全数
        return true;
    }else return false;
}
int main(){
    int n;
    while(cin>>n){
        int count=0;//统计完全数个数
        for(int i=1;i<=n;i++){//遍历一遍n以内的所有数字
            vector<int> factors=fin_factors(i);//找因子
            if(isPerfect(factors,i)){//判断是否为完全数
                count++;
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{2})$ ，最坏情况是检查n是否为完全数的时候，外循环为 $O (n)$ ，枚举n的所有因子时复杂度也为 $O (n)$ 。
空间复杂度： $O (1)$ ，只用了常数空间。

方法二：

根据枚举法找的完全数我们可以发现，完全数的个数非常的少，我们可以列举出500000内的所有完全数，划分为多个区间，确定每个区间的完全数个数，每次输入n的时候判断n的范围，输出这个范围内的完全数个数。但是这个方法是要有先验判断的，不是最佳方法。

具体做法：

#include<iostream>

using namespace std;

int main(){
    int n;
    while(cin>>n){
        if(n<=0||n>500000) return -1;//超过范围
        else if(n<6) cout<<0<<endl;//6以内没有完全数
        else if(n<28) cout<<1<<endl;//28以内只有一个完全数28
        else if(n<496) cout<<2<<endl;//496以内只有两个完全数28，496
        else if(n<8128) cout<<3<<endl;//8128以内只有三个完全数28，496，8128
        else cout<<4<<endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (1)$ ，只需简单判断，空间复杂度为常数。
空间复杂度： $O (1)$ ，只有常数空间。

题解 | #完全数计算#

题目的主要信息：

方法一：

方法二：