相亲数问题

相亲数（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;
}
复制代码