HJ56 完全数计算

题目描述

完全数(Perfect number),又称完美数或完备数,是一些特殊的自然数。

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

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

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

方法一:暴力算法

解题思路

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

解题代码

#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(N2)O(N^2)

空间复杂度:使用factors存储因子,因此空间复杂度为O(n)O(n)

方法二:巧妙解法

解题思路

对于完全数的定义,我们通过搜集资料,可以发现其个数非常少,因此根据其出现的规律,我们对于输入的n进行判断,然后让其对应在完全数为定值的区间内并进行输出。这里完全数我们知道有28、496和8128,然后将其与n进行比较,最后输出结果即可。 alt

解题代码

#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)