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;
}
复杂度分析
时间复杂度:两层循环,时间复杂度为。
空间复杂度:使用factors存储因子,因此空间复杂度为
方法二:巧妙解法
解题思路
对于完全数的定义,我们通过搜集资料,可以发现其个数非常少,因此根据其出现的规律,我们对于输入的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;
}
复杂度分析
时间复杂度:无循环,时间复杂度为
空间复杂度:常数级空间,因此空间复杂度为