相亲数问题

article/2025/10/8 10:06:00

相亲数（Amicable Pair），又称亲和数、友爱数、友好数，指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。毕达哥拉斯曾说：“朋友是你灵魂的倩影，要像220与284一样亲密。” 例如220与284： 220的全部因数（除掉本身）相加是：1+2+4+5+10+11+20+22+44+55+110=284 284的全部因数（除掉本身）相加的和是：1+2+4+71+142=220 亲和数中可轻易推出，一方的全部约数之和与另一方的全部约数之和相等。(此叙述不可逆，不能用来判断是否为亲和数) 220的全部约数之和是：1+2+4+5+10+11+20+22+44+55+110+220 = 284+220 = 504 284的全部约数之和是：1+2+4+71+142+284 = 220+284 = 504

问题：求3000以内的相亲数简单方法：

#include <iostream>
#include <stdio.h>const int maxn=30000+3;int sum[maxn];
//计算m除本身外全部约数之和
int sumnum(int m){int n=0;for(int i=1;i<=m/2;i++){if(!(m%i)){n+=i;}}return n;
}int main()
{sum[1]=0;for(int i=2;i<=30000;i++){sum[i]=sumnum(i);}for(int i=2;i<=30000;i++){//防止数组越界if(sum[i]>30000) continue;//防止出现像6这样全部约数之和等于本身if(sum[i]!=i && sum[sum[i]]==i){cout<< i<<" "<<sum[i]<<endl;//防止重复打印输出sum[i]=1;}}return 0;
}
复制代码

该方法的时间复杂度比较高。
实际计算 m 的所有约数，只需要计算 $\sqrt m$ 次即可例如：

100
1 * 100
2 * 50
4 * 25
5 * 20
10 * 10
sum[100] = 1+2+50+4+25+5+20+10
复制代码

除了平方以外不会有重复出现
完整程序

#include <iostream>
#include <stdio.h>const int maxn=30000+3;int sum[maxn];
//计算m除本身外全部约数之和
int sumnum(int m){//自2开始每个数都有一个为1的约数int n=1;int i;for(i=2;i*i<m;i++){if(!(m%i)){n+=i;n+=(m/i);}}//如果m为平方数，则其开方只能使用一次if(i*i==m){n+=i;}return n;
}int main()
{sum[1]=0;for(int i=2;i<=30000;i++){sum[i]=sumnum(i);}for(int i=2;i<=30000;i++){//防止数组越界if(sum[i]>30000) continue;//防止出现像6这样全部约数之和等于本身if(sum[i]!=i && sum[sum[i]]==i){cout<< i<<" "<<sum[i]<<endl;//防止重复打印输出sum[i]=1;}}return 0;
}
复制代码