完全数(Perfect number),又称完美数或完备数,是一些特殊的自然数。它所有的真因子(即除了自身以外的约数)的和(即因子函数),恰好等于它本身。如果一个数恰好等于它的因子之和,则称该数为“完全数”。
寻找完美的数
题目描述:所谓完美的数是这个数除了它自身之外,所有因子的和等于该数。
例如: 28,其因子包括:1,2,4,7,14,28,除了28之外,1+2+4+7+14 = 28
再例如:6,其因子包括:1,2,3,6 除了6之外,1+2+3 = 6
寻找 1~10000之间的完美的数。
法一程序代码如下:
#include<stdio.h>
int fun_perfect(int number)
{
int i,sum=0;
for(i=1;i<number;i++)
{
if(number%i==0){
sum+=i;
}
if(sum>number)
return 0;
}
return sum==number;
}
int main()
{
int i;
for(i=2;i<10000;i++)
{
if(fun_perfect(i))
printf("%d\n",i);
}
return 0;
}
很明显,此法较为暴力,当搜寻范围较小时,运行的效率可以被接受,但倘若所搜寻的范围高达十几万,此法运行效率较低需十几秒。
法二:优化暴力搜索程序代码如下:
#include<stdio.h>
#include<math.h>
int fun_perfect(int number)
{
int i,sum=1;
for(i=2;i*i<number;i++)
{
if(number%i==0)
{
sum+=i;
if(i*i!=number)
{
sum+=number/i;
}
}
}
return sum==number;
}
int main()
{
int i;
for(i=2;i<100000;i++)
{
if(fun_perfect(i))
printf("%d\n",i);
}
return 0;
}
法三:利用推导公式:
大数学家欧拉曾推算出完全数的获得公式:如果p是质数,且2p-1也是质数,那么(2p-1)X2^(p-1)便是一个完全数。
例如p=2,是一个质数,2p-1=3也是质数,(2p-1)X2^(p-1)=3X2=6,是完全数。
例如p=3,是一个质数,2p-1=7也是质数,(2p-1)X2^(p-1)=7X4=28,是完全数。
例如p=5,是一个质数,2p-1=31也是质数,(2p-1)X2^(p-1)=31X16=496是完全数。
但是2p-1什么条件下才是质数呢?事实上,当2p-1是质数的时候,称其为梅森素数。到2013年2月6日为止,人类只发现了48个梅森素数,较小的有3、7、31、127等。
程序代码如下:
#include<stdio.h>
#include<math.h>
int main()
{
int arr[5]={2,3,5,7,11};
for(int i=0;i<5;i++)
{
int num=pow(2,arr[i]-1)*(pow(2,arr[i])-1);
if(num<100000){
printf("%d\n",num);
}
}
return 0;
}