完美数的算法设计（C语言）

ゝ一纸荒年。 2022-03-30 14:00 283阅读 0赞

完全数（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;
    }