复试算法练习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语言中采用判断是否为完全数的时候，可以先对需要运算的算法计时，通过计时来判断运算的速度，从而确定算法的速度快慢，然后根据题目要求，可以采用直接加和因子的方法用定义求解完全数，也可以利用梅森素数的求解，先求解梅森素数，然后利用梅森素数求完全数的算法来计算最终结果，采用不同的原理可以使算法的时间复杂度降低，加快算法输出速度，也是可以让我们看到更多的方法来针对具体问题，通过不同角度具体分析，具有良好的借鉴意义。

标签： 时间复杂度 空间复杂度