|
2.5 完全数
正整数n的所有小于n的不同正因数之和若等于n本身，称数n为完全数。
例如，6的正因数为1,2，3，而6=1=2+3，则6是一个完全数。
试求指定区域内的完全数。
1、算法分析
对指定区域中的每一个数A实施穷举判别。根据完全数的定义，为了判别正数A是不是完全数，用试商法找出A的所有小于A的因数K。显然，1<=K<=A/2。注意到1是任何整数的因数，先把因数1确定下来，即因数和S赋初值1，然后设置K从2到A/2的循环，由表达式A/K判别K是否是A的因数，并求出A的因数累加和S。最后若满足条件A=S说明A是完全数，作打印输出。把n的因数从1开始，由小到大排列，写成和式。
程序代码如下：
#include
void main()
{
int a,s,k;
int n=0;
printf("(2,10000)中的完全数: ");
for(a=2;a<=10000;a++)
{
s=1;
for(k=2;k<=a/2;k++)
if((float)a/k==a/k) s=s+k;
if(s!=a)goto A;
n=n+1;
printf("%d:%d=1",n,a);
for(k=2;k<=a/2;k++)
if((float)a/k==a/k)printf("+ %d",k);
printf("\n");
A:;
}
}
程序运行结果如下：
----------------------------------
改进的程序：
上述程序求正因数K的试商循环中存在着大量的无效循环，使得程序运行时间较长。为了缩短运行时间 ，可以从减少K的循环次数入手。注意到数A若为非平方数，它的大于1小于A的因数成对出现，每一对中的较小因数要小于A的平方根。若数A愉为整数B的平方，此时B为A的一个因数而不是一对。因此，在作赋值B+SQR(A)之后，K的循环可以设置从2到B来完成，大大减少K的循环次数，缩短程序的运行时间。
程序代码如下：
#include
#include
void main()
{
int b,i,k,m,n,c[100];
long a,s,x,y,d[100];
printf("求区间[x,y]中的完全数.\n");
printf("请输入整数x,y: ");
scanf("%ld,%ld",&x,&y);
printf("[%ld, %ld]中的完全数有：\n",x,y);
for(a=x;a<=y;a++)
{
s=1;n=0;b=(int)sqrt(a);
for(k=2;k<=b;k++) /*试商寻求a的因数k*/
if(a%k==0)
{
s=s+k+a/k;n++;c[n]=k;d[n]=a/k;} /*a/k也是a的因数*/
if(a==b*b){s=s-b;m=n-1;} /*如果a=b^2，去掉一个b的重复因数*/
else m=n;
if(a==s)
{
printf("%ld=1 ",a); /*分两段从小到大打印因数之和*/
for(i=1;i<=n;i++)
printf("+ %d",c[i]);
for(i=m;i>=1;i--)
printf("+ %ld",d[i]);
if(a%2==1)printf("奇完全数!");
printf("\n");
}
}
}
程序运行结果如下：
说明：
迄今为止，寻找到的完全数都是偶完全数。是否存在奇完全数还是一个难题，既不能证明，也不能否定。因此在以上程序中如果找到的完全数是数(a%2==1)时，作“奇完全数!”的特别标记
|
