题解 | #完全数计算#

HJ56 完全数计算

题目描述

完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。

它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。

例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。

输入n，请输出n以内(含n)完全数的个数。

方法一：暴力算法

解题思路

对于方法一，我们直接使用暴力的方法进行遍历，首先对于每个小于等于n的整数我们找出其所有因子，即用一个for循环看起取余是否为0即可，然后对找到的因子（除去其自身外）进行相加，如果等于这个整数，则为完全数。否则，不是完全数。

解题代码

#include<bits/stdc++.h>
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)O(N^2)$。

空间复杂度：使用factors存储因子，因此空间复杂度为$O(n)O(n)$

方法二：巧妙解法

解题思路

对于完全数的定义，我们通过搜集资料，可以发现其个数非常少，因此根据其出现的规律，我们对于输入的n进行判断，然后让其对应在完全数为定值的区间内并进行输出。这里完全数我们知道有28、496和8128，然后将其与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)$

空间复杂度：常数级空间，因此空间复杂度为$O(1)O(1)$