欧拉工程12题

欧拉工程12题原题：

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th 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?

 

翻译：

自然数累加生成的数叫三角数（不知道能不能像这样翻译）。如：第7个三解数为1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

前十个序列应该是：

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

列出前七个三角数的因数如下：

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

 

可以看到28是第一个因数超过5个的三角数

第一个因数超过500个的三角数是多少？

 

关键：

a=(b^i)*(c^j)*(d^k)*.....(b的i次方乘以c的j次方....,b,c,d....为质数);

则a的因数的个数为：

count=(i+1)*(j+1)*(k+1).....

可以证明上式是成立的.

 

C代码如下：

#include <stdio.h>
int getFactorCount(int num){/*计算因数个数*/
    int count=1;/**因数的个数**/
    int i=2;/**遍历变量*/
    int tmp = 1;/**相同质因数个数临时存放变量**/
    int flag=0;/**标识上一个质因数的值**/
    while(!(num<i)){/***计算出A的质因数***/
        if(num%i==0){/**如果成立则i应该是mun的一个质因数**/
            num=num/i;
            if(flag!=i){/**当前质因数的值与上一个是否一样**/
                count*=tmp;
                tmp=2;
                flag=i;
                if(num==1)
                    count*=tmp;   
            }
            else
                tmp++;
        }else
            i++;
    }
    return count;
}
int main(char * args){
    int a=2;
    int count=0;
    do{
        count = getFactorCount(a*(a+1)/2);
        a++;
    }while(count<500);
    printf("%d\n",(a-1)*a/2);/***因为多执行了一步a++所以所求值应为(a-1)*a/2***/
}

结果：76576500

 

总结：

开始的时候想了很多方法都是想怎么求因数，但没有把关键的问题 质因数与因数的关系分析清楚，走了很多弯路。像这一类题还是数学功底比程序功底要重要一些。