题目大意:

d(n)定义为n 的所有真因子(小于 n 且能整除 n 的整数)之和。 如果 d(a) = b 并且 d(b) = a, 且 a不等于b, 那么 a 和 b 就是一对相亲数(amicable pair),并且 a 和 b 都叫做亲和数(amicable number)。

例如220的真因子是 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 和 110; 因此 d(220) = 284. 284的真因子是1, 2, 4, 71 和142; 所以d(284) = 220.

计算90000以下所有亲和数之和。(原题10000)

其实思想都是从这里借鉴的。

#include<stdio.h>
#include<math.h>
#include<time.h>
int a[100001]={0};
void sieve(int n)//计算n以内的质数
{
    for(int i=2;i<=n;i++)
      for(int j=2;j<=n/i;j++)
        a[i*j]=1;
    int j=1;
    for(int i=2;i<=n;i++)
      if(a[i]==0)
        a[j++]=i;
    a[0]=j; //保存质数个数
    printf("%d内质数个数%d\n",n,j);
}
int FactorSum2(int n)  //计算n的所有小于n的因数和
{
    int i;
    int sum=1;
    int x=n;
    for(int j=1;j<a[0];j++)
    {
    int c=0;
    while(x%a[j]==0)
    {
        c=c+1;
        x=x/a[j];

    }
    sum*=(pow((double)a[j],c+1)-1)/(a[j]-1);
    if(x==1)break;
    }
    return sum-n;
}

int FactorSum(int n)  //计算n的所有小于n的因数和
{
    int i;
    int sum=1;
    for(i=2; i<=n/2; i++)
    {
        if(n%i==0)
            sum+=i;
    }
    return sum;
}

int main()
{
    int t,i=2;
    int sum=0;
    //方法1
    int tm=clock();
    while(i<90000)
    {
        t=FactorSum(i);
        if(t!=i && FactorSum(t)==i) 
            {sum+=i;/*printf("%d %d %d\n",i,t,i-t>0?i-t:t-i);*/}
        i++;
    }
    printf("%d %dms\n",sum,clock()-tm);
    tm=clock();
    sieve(90000);
    //方法2
    i=2;sum=0;
     while(i<90000)
    {
        t=FactorSum2(i);
        if(t!=i && FactorSum2(t)==i) 
            {sum+=i;/*printf("%d %d %d\n",i,t,i-t>0?i-t:t-i);*/}
        i++;
    }
    printf("%d %dms\n",sum,clock()-tm);

    return 0;
}

运行结果在vc和g++有很大区别。

D:\>cl p21e.cpp -O2 -o p21e.exe
用于 x86 的 Microsoft (R) C/C++ 优化编译器 17.00.51106.1 版版权所有(C) Microsoft Corporation。保留所有权利。

cl: 命令行 warning D9035 :“o”选项已否决,并将在将来的版本中移除
p21e.cpp
Microsoft (R) Incremental Linker Version 11.00.51106.1
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:p21e.exe
/out:p21e.exe
p21e.obj

D:\>p21e
852810 19188ms
90000内质数个数8714
852810 1419ms
----------------------------------

D:\>g++ p21e.cpp -O2 -o p21e.exe

D:\>p21e
852810 18361ms
90000内质数个数8714
852810 6131ms

原来还想做的一个优化是,因为亲和数总是成对出现,所以得到一个时,就可以去掉另一个,但收效甚微,因为它的个数和非亲和数比太微不足道,可以去掉;/*printf("%d %d %d\n",i,t,i-t>0?i-t:t-i);*/的注释来查看。

补充:上面的程序有个bug,出在sum*=(pow((double)a[j],c+1)-1)/(a[j]-1);一行,浮点运算不能保证整除。

    int c=0;
    while(x%a[j]==0)
    {
        c=c+1;
        x=x/a[j];

    }
    sum*=(pow((double)a[j],c+1)-1)/(a[j]-1);
改为
    int c=0;
    int prod=1;
    while(x%a[j]==0)
    {
        c=c+1;
        x=x/a[j];
        prod*=a[j];

    }
    sum*=(prod*a[j]-1)/(a[j]-1);

现在,两种编译器的比较正常了。

D:\>cl p21a.cpp -o p21a.exe -O2
用于 x86 的 Microsoft (R) C/C++ 优化编译器 19.00.24215.1 版
版权所有(C) Microsoft Corporation。保留所有权利。

cl: 命令行 warning D9035 :“o”选项已否决,并将在将来的版本中移除
p21a.cpp
Microsoft (R) Incremental Linker Version 14.00.24215.1
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:p21a.exe
/out:p21a.exe
p21a.obj

D:\>p21a
852810 9969ms
90000内质数个数8714
852810 794ms

D:\>g++ p21a.cpp -o p21a.exe -O2

D:\>p21a
852810 10030ms
90000内质数个数8714
852810 774ms

方法3,把每个因数和都记录下来,就不用计算2遍了。

    //方法3 空间换时间
    i=2;sum=0;
    int b[100001]={0};
     while(i<90000)
    {
        int j=FactorSum2(i);
        if (j==1 || j>=90000 || j<0){b[i]=0;}
        else {b[i]=j;}
        i++;
    }
    i=2; printf("**");
     while(i<90000)
    {
        if(b[i]!=i && b[i]<90000) 
        if(b[b[i]]==i)
            {sum+=i;/*printf("%d %d %d\n",i,t,i-t>0?i-t:t-i);*/}
        i++;
    }
    printf("%d %dms\n",sum,clock()-tm);
运行结果
852810 421ms

补充,由于运算过程中大数用整型变量会溢出,改为long long,同时做了一些简化

int FactorSum2(int n)  //计算n的所有小于n的因数和
{
    int i;
    int sum=1;
    int x=n;
    for(int j=1;j<a[0];j++)
    {
    //int c=0;
    long long prod=1;
    while(x%a[j]==0)
    {
        //c=c+1;
        x=x/a[j];
        prod*=a[j];
        if(x==1)break;

    }
    if(prod!=1)sum*=(prod*a[j]-1)/(a[j]-1);
    if(x==1)break;
    }
    return sum-n;
}
结果
D:\>cl p21b.cpp -o p21b.exe -O2
用于 x86 的 Microsoft (R) C/C++ 优化编译器 19.00.24215.1 版
版权所有(C) Microsoft Corporation。保留所有权利。

cl: 命令行 warning D9035 :“o”选项已否决,并将在将来的版本中移除
p21b.cpp
Microsoft (R) Incremental Linker Version 14.00.24215.1
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:p21b.exe
/out:p21b.exe
p21b.obj

D:\>p21b
852810 9920ms
90000内质数个数8714
852810 358ms
**852810 247ms

上面调试溢出情况时发现,问题都出在n本身质数的情况,而质数到最后1步才除以自身,很耗时,所以可以作如下修改:

int FactorSum3(int n)  //计算n的所有小于n的因数和
{
    int i;
    int sum=1;
    int x=n;
    for(int j=1;j<a[0];j++)
    {
    //int c=0;
    long long prod=1;
    //因为如果到了sqrt(n)还没找到质因数,那n自己就是质数
    if(sum==1 && a[j]*a[j]>n)return 1;
    while(x%a[j]==0)
    {
        //c=c+1;
        x=x/a[j];
        prod*=a[j];
        if(x==1)break;

    }
    if(prod!=1)sum*=(prod*a[j]-1)/(a[j]-1);
    if(x==1)break;
    }
    return sum-n;
}
运行时间
**852810 134ms

如果根本不对质数调用FactorSum函数,预先作标记

    //方法4跳过质数n
    i=2;sum=0;
    int b1[100001]={0};
    for(int j=1;j<a[0];j++)b1[a[j]]=1; //预先标记
     while(i<90000)
    {
        if(b1[i]==1){i++;continue;}
        int j=FactorSum3(i);
        if (j==1 || j>=90000 ){b1[i]=0;}//printf("%d %d \n",i,j);}
        else {b1[i]=j;}
        i++;
    }
    i=2; printf("**");
     while(i<90000)
    {
        if(b1[i]!=i && b1[i]<90000) 
        if(b1[b1[i]]==i)
            {sum+=i;/*printf("%d %d %d\n",i,t,i-t>0?i-t:t-i);*/}
        i++;
    }
    printf("%d %dms\n",sum,clock()-tm);

结果
**852810 125ms

看了这个6年前的帖子。即使不用数学公式,也不用空间,就能达到很好的效果。

int FactorSum4(int n)  //计算n的所有小于n的因数和
{
    int i;
    int sum=1;
    for(i=2; i<=sqrt(n); i++)
    {
        if(n%i==0)
            sum+=(i+n/i);
    }
    return sum-(((i-1)*(i-1)==n)?(i-1):0);
}
int FactorSum5(int n)  //计算n的所有小于n的因数和
{
    int i;
    int sum=1;
    int step=1+(n%2);
    for(i=1+step; i<=sqrt(n); i+=step)
    {
        if(n%i==0)
            sum+=(i+n/i);
    }
    return sum-(((i-step)*(i-step)==n)?(i-step):0);
}

--结果
852810 9884ms
852810 104ms  -- FactorSum4
852810 86ms  -- FactorSum5
90000内质数个数8714
852810 357ms
**852810 248ms
**852810 123ms
--852810 48ms -- FactorSum5和利用空间和跳过质数方法结合