复试算法练习Day14——完全数计算
题目描述
完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。
它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
(资料图片)
例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。
输入n，请输出n以内(含n)完全数的个数。
数据范围： 1 \le n \le 5 \times 10^{5} \1≤n≤5×105
输入描述：
输入一个数字n
输出描述：
输出不超过n的完全数的个数
示例1
输入：
1000
输出：
3
思路
思路一：通过完全数的要求根据定义如果一个数恰好等于它的因子之和，则称该数为"完全数"，则按要求将一个数的因子加和与其本身对比，如果相同则正确，不同则失败
思路二：通过梅森素数来确定最终结果是不是完全数，如果(2^p-1)是素数，那么它就是梅森素数，再根据用(2^p-1)*2^(p-1)，这个就是完全数
具体实现
//写C语言情况下的运算
//根据定义计算
//如果一个数恰好等于它的因子之和，则称该数为"完全数"
#include<iostream>
#include<time.h>
//计算出Rmax以内的所有完全数
#define Rmax 100000
//名字空间初始化
using namespace std;
void main() {
//求解其完全数的因子
for (int i = 3; i <= Rmax; ++i) {
//计算所有因子的和
int sum = 1;
for (int j = 2; j < i; ++j) {
if (i%j == 0) {
//说明j是i的因子
//并对因子求和
sum += j;
}
}
//判断和是否等于数本身
if(sum==i){
cout << i << endl;
}
}
system("pause");
}
//方案二：通过梅森素数来确定最终结果是不是完全数
//如果(2^p-1)是素数，那么它就是梅森素数，
//再根据用(2^p-1)*2^(p-1)，这个就是完全数
#include<iostream>
#include<time.h>
#include<math.h>
//定义一个极大的数
#define max 1000000000
using namespace std;
//素数初始化
bool Prime(int prime);
void main() {
//设置时钟来显示运算速度，来表示时间复杂度
clock_t start, end;
start = clock();
//判断一个数是否为梅森素数
//如果是则将其因子求和
for (int p = 2;; ++p) {
int perfect = (pow(2,p) - 1) * pow(2 ,p - 1);
if (perfect > max)break;
int prime = pow(2, p) - 1;
if (Prime(prime))cout << perfect << endl;
}
//求解梅森素数算法所需时间输出
end = clock();
float time = (float)(end - start) / 1000;
cout << "time is" << time << "s" << endl;
system("pause");
}
//求解是否为质数
bool Prime(int prime) {
//假设选择的数为质数
bool choice = true;
int k = sqrt((float)prime);
//判断因子之和和本身是否相同
for (int j = 2; j <= k; ++j) {
//如果不是质数，则输出错误返回
if (prime % j == 0) {
choice = false;
break;
}
}
return choice;
}
时间复杂度
对于方案一，在遍历的时候采用了两次for循环首先遍历出因子，然后将因子加和，所以时间复杂度为O(n^2),空间复杂度也为O(n)
对于方案二，采用先判断是否为梅森素数，之后采用素数来判断是否为完全数，只遍历了一次，所以时间复杂度为O(n),空间复杂度也为O(n)
小结
在C语言中采用判断是否为完全数的时候，可以先对需要运算的算法计时，通过计时来判断运算的速度，从而确定算法的速度快慢，然后根据题目要求，可以采用直接加和因子的方法用定义求解完全数，也可以利用梅森素数的求解，先求解梅森素数，然后利用梅森素数求完全数的算法来计算最终结果，采用不同的原理可以使算法的时间复杂度降低，加快算法输出速度，也是可以让我们看到更多的方法来针对具体问题，通过不同角度具体分析，具有良好的借鉴意义。
