C趣味程序(二)(11)完全数

文章作者 100test 发表时间 2007:03:10 17:38:43
来源 100Test.Com百考试题网

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").
}
}
}