[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之和
难在如何求一个数n的约数,观察 28: 1,2,4,7,14,28 除了1和28(n本身)外,其它约数中,关键约数是2和7,剩下的则是关键约数的倍数
所以,先求出关键的这些约数,然后再求约数的倍数,而关键的约数也就是质因数(prime factor),求一个数的质因数参考003题。
get_divisors_count这个函数是上述算法的粗糙版本,
}
其中有个问题是如何记录已经找到的约数,由于有可能存在重复查找(比如14是2的倍数也是7的倍数,所以重复查找了)则不能简单地累计,
要记录这些数,最简单的方法是用hashtable之类的,但标准C里面没有内置,所以我用了一个数组,数组下标表示约数,值为1则表示找到了。
上述方法是可以改进的,然后得到了get_divisors_count2这个函数,理论基础来自于这里:http://mathforum.org/library/drmath/view/55843.html
于是我们得到更高效的函数:
注:当完成题目后,对于某些题,官方网站会给出参考答案,在我的博客里不会将官方答案贴出来,仅仅会写下我自己当时的思路,除非两者不谋而合。另外,如果你有更好的思路,请留言告诉我,我非常乐意参与到讨论中来。