[Project Euler] 来做欧拉项目练习题吧: 题目012

时间:2023-02-22 22:43:51

                                   [Project Euler] 来做欧拉项目练习题吧: 题目012

                                                       周银辉 

 

 

问题描述: 

The sequence of triangle numbers is generated by adding the natural numbers. So the 7thtriangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1 : 1
 3 : 1,3
 6 : 1,2,3,6
10 : 1,2,5,10
15 : 1,3,5,15
21 : 1,3,7,21
28 : 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

 

 

问题分析:

 

题目要求找出第一个拥有超过500个约数的三角数。

 

首先,求第i个三角数很容易,其是1~i之和

long get_trangle_number(int i)
{
return ((long)(1+i)*i)/2;
}

难在如何求一个数n的约数,观察 28: 1,2,4,7,14,28 除了1和28(n本身)外,其它约数中,关键约数是2和7,剩下的则是关键约数的倍数

所以,先求出关键的这些约数,然后再求约数的倍数,而关键的约数也就是质因数(prime factor),求一个数的质因数参考003题

get_divisors_count这个函数是上述算法的粗糙版本,

int get_divisors_count(int number)
{
if(number<1)
{
return 1;
}

int count     = 0;
int factor    = 2;
int n         = number;
int buffer_sz = number+1;
int i;

int array[buffer_sz];
for(i=0; i<buffer_sz; i++)
{
array[i]=0;
}
array[1]      = 1;
array[number] = 1;

while(n>1)
{
if(n%factor==0)
{
//printf("prime factor found: %d\n", factor);

array[factor]=1;
i=2;
while(number%(i*factor)==0)
{
array[i*factor]=1;
i++;
}
while(n%factor==0)
{
n/=factor;
}
}

factor++;
}

        //printf("divisors of %d: ", number);
for(i=0; i<buffer_sz; i++)
{
if(array[i]==1)
{
//printf("%d ", i);
count++;
}
}
return count;

} 

其中有个问题是如何记录已经找到的约数,由于有可能存在重复查找(比如14是2的倍数也是7的倍数,所以重复查找了)则不能简单地累计,

要记录这些数,最简单的方法是用hashtable之类的,但标准C里面没有内置,所以我用了一个数组,数组下标表示约数,值为1则表示找到了。

数组对于比较小的数没问题,但数太大的话,一是遍历是效率低下,二是如果在栈上分配的容易导致内存错误。 

 

 

上述方法是可以改进的,然后得到了get_divisors_count2这个函数,理论基础来自于这里:http://mathforum.org/library/drmath/view/55843.html 

于是我们得到更高效的函数:

int get_divisors_count2(long number)
{
if(number<1)
{
return 1;
}
int count     = 1;
int factor    = 2;
long n        = number;
int i, t;
while(n>1)
{
if(n%factor==0)
{
//printf("prime factor found: %d\n", factor);
t = 1;
while(n%factor==0)
{
t++;
n/=factor;
}
count *= t;
}
factor++;
}
return count;
}
 

 

注:当完成题目后,对于某些题,官方网站会给出参考答案,在我的博客里不会将官方答案贴出来,仅仅会写下我自己当时的思路,除非两者不谋而合。另外,如果你有更好的思路,请留言告诉我,我非常乐意参与到讨论中来。