Project Euler——Problem 23

daybreakcx posted @ 2009年7月25日 06:08 in Prject Euler , 1162 阅读

原题与答案：

Problem 23

02 August 2002

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Answer:4179871

分析与解答：

题目中先定义了一种数，这种数的特点是他的所有小于本身的约数的和大于本身，然后阐述了一个结论，任何一个大于28123的整数都能写成两个这种数的和，要我们求不能写成两个这种数的和的数的总和。很自然地我们想到了一种解法，先枚举所有的那种数，然后获得所有小等于28123的两个这种数的和，最后把没出现的全部加起来就可以了。首先是这种数的枚举，由于12是最小的，所以枚举到28111即可，对于每个数判断小于他的约数的和是否大于本身。那么约数怎么求呢？在前面的文章中我们已经说过了，就是质因数分解，然后利用公式求得，这里就不再重复了，这样我们就能枚举出这些数了。最后我们要做的是求出所有是两个这种数的和的数。我们用一个bool数组表示一个数是否可以表示为两个这种数的和，然后我们利用二次时间把所有可以表示为两个这种数和的数标示，最后线型扫描一次就能完成任务了。我的程序员代码如下所示：

#include<stdio.h>
#include<string.h>
bool nprime[168],can[28112];
int a[50],s[7000],i,j,ans;
int calc(int s)
{
int i,ret=1,t;
for (i=1;s!=1&&i<=a[0];i++)
{
t=1;
while (s%a[i]==0)
{
s/=a[i];
t*=a[i];
}
ret=ret*(t*a[i]-1)/(a[i]-1);
}
if (s!=1) return ret*(s+1);
else return ret;
}
int main()
{
memset(nprime,false,sizeof(nprime));
a[0]=0;
for (i=2;i<=167;i++)
if (!nprime[i])
{
a[++a[0]]=i;
for (j=i*i;j<=167;j+=i)
nprime[j]=true;
}
s[0]=0;
for (i=1;i<=28111;i++)
if (calc(i)>(i<<1))
s[++s[0]]=i;
memset(can,false,sizeof(can));
for (i=1;i<=s[0];i++)
for (j=1;j<=s[0];j++)
if (s[i]+s[j]>28111) break;
else can[s[i]+s[j]]=true;
for (i=1;i<=28111;i++)
if (!can[i]) ans+=i;
printf("%d\n",ans);
return 0;
}