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

article/2025/10/8 9:59:40

“相亲数”的介绍

在数学中，“相亲数”是指一对“你中有我，我中有你”的数字，其特点是：
彼此的全部约数和（本身除外）与另一方相等。

例如：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");}}
}