关于“相亲数”的算法实现

时间:2022-04-15 11:11:20

“相亲数”的介绍

在数学中,“相亲数”是指一对“你中有我,我中有你”的数字,其特点是:
彼此的全部约数和(本身除外)与另一方相等

例如:220和284就是一对相亲数。

220的全部约数和(除掉220本身)相加是:
1+2+4+5+10+11+20+22+44+55+110 = 284

同样,284的全部约数(除掉284本身)相加的和为:
1+2+4+71+142 = 220

关于“相亲数”的研究从古至今都未曾中断过,这篇文章是我将老师所讲的提炼一下并给出拓展的算法。

C语言的算法实现

#define N 10000
main()
{
 int i,j,k; unsigned s[N];
 clrscr();//清屏

 for(i=2;i<N;i++) for(j=1,s[i]=0;j<i;j++) if(i%j==0) s[i]+=j;

 for(i=2;i<N;i++)
 for(j=i+1;j<N;j++)
 if((i==s[j])&&(j==s[i]))
    {
     printf("%d: ",i);
     for(k=1;k<i;k++) if(i%k==0) printf("%d ",k); printf("\n");
     printf("%d: ",j);
     for(k=1;k<j;k++) if(j%k==0) printf("%d ",k); printf("\n\n");
    }
}

上面的代码只需要导入函数库,即在开头加上include <stdio.h>就可运行。

程序用来输出10000以内的相亲数,运行结果如下:

关于“相亲数”的算法实现

算法分析

首先声明变量,其中变量名为s的表示含有N个无符号类型数据的数组。然后两个for循环用来计算10000以内每个数的所有约数和,并放入数组中。下面两个for中j变量的初始值为i+1,这是为了防止出现220,284和284,220的重复情况,if语句判断是否约数和等于对方,printf语句输出整个过程。

下面给出j初始值为2的运行结果:

关于“相亲数”的算法实现

以上只是截取了一部分,可以看出有重复的情况,并且运行时间要比原来的久,效率低。

修改版

下面是我们老师布置的作业,要求将后面的两个for循环变成一个循环,我的思路是用一个循环遍历数组下标,同时将数组中每个值赋给另一个变量,这个变量也作为下标来做判断,具体算法如下:

#define N 10000
main()
{
 int i,j,k; unsigned s[N];
 clrscr();//清屏

 for(i=2;i<N;i++) for(j=1,s[i]=0;j<i;j++) if(i%j==0) s[i]+=j;

 for(i=2;i<N;i++)
 {
    j=s[i];
    if(j>N) continue;//if(i==s[j]&&j>i)
    {
     printf("%d: ",i);
     for(k=1;k<i;k++) if(i%k==0) printf("%d ",k); printf("\n");
     printf("%d: ",j);
     for(k=1;k<j;k++) if(j%k==0) printf("%d ",k); printf("\n\n");
    }
 }
}

一开始代码中的①处我写在了下面的for循环中,结果这样在i为5000多的某处会导致j的值超过一万,数组下标越界,后来单独写出来就行了。运行结果与第一次结果相同。

其实随着N的值的增加,数组的开销会很大,运行结果的时间会很长,效率很低,目前没有想到更好的算法,以后想到了再补充。