ProjectEuler解题笔记-Problem 12
2010年11月20日
没有评论
ProjectEuler是与mathchallenge类似的oj系统，提供一些数学和计算机相关的问题。题目难度从易到难都有，工作之余，做一两道题目也是很不错的休闲，还能重拾遗忘的数学知识。另外网站还提供了问题分析，看看别人的优化思路，也是一种提高。
题目
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle 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?
思路
题目很好理解：首先定义了什么叫triangle number，然后提出问题：找出含有500个因子的第一个triangle number。
Naive方法
暴力分解，很快代码就能写出来。
// 暴力计算因子个数
int get_factor_count( uint64 num )
{
uint64 count = 0;
for ( uint64 i = 1; i< num; i ++)
{
if (i*i > num)
{
break;
}
if (num % i ==0)
{
count ++;
if (i * i != num)
{
count ++;
}
}
}
return count;
}
void problem12()
{
uint i=2;
do{
if( get_factor_count(i) >= 500 ) {
printf("%u\n", i);
return;
}
else if( i % 10000 == 0 ) {
printf( "%d %u\n", i, get_factor_count(i) );
}
}while( i++ );
}
但跑到1分钟还没出结果，无奈的cancel掉。
分析优化
根据题意，三角数是从1累加的值，根据等差公式，第n个triangle num的值为n(n+1)/2。发现这里面有些文章可以做：
1. n和n+1必然有一个为偶数，也就是说，它们中的一个会被2整除。
2 . 除1外，n和n+1没有公共因子。
因此，我们可以得到这个数的因子个数为
P(Tn)=P(n/2)*P(n+1) n为偶数 P(Tn)=P(n)*P( (n+1)/2 ) n为奇数
根据这一思路，我们就能得到新的函数。这样我们只需要平方根级别的计算。
void problem12()
{
const static int N = 100000;
int a[N];
for( int i = 2; i<N; i++ )
{
if( i % 2 ==0 )
a[i]=get_factor_count(i/2);
else
a[i]=get_factor_count(i);
}
for( int i = 2; i<N-1; i++ )
{
if( a[i]*a[i+1]>500)
{
printf("%lu\n",i*(i+1)/2 );
break;
}
}
}
经过优化，在我的机器上500ms就计算出了答案。
进一步优化
由于时间已经满足要求，就未进一步优化。
如果需要，下手点应该是get_factor_count函数了。参考这篇文章。
