12. 500개 이상의 약수를 가진 트라이앵글 숫자는 무엇인가

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?

트라이앵글 숫자의 연속이라고 하는 것은 자연수를 추가해나가면서 생성되는 것이다. 

예를들어 일곱번째 트라이앵글 숫자는

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 이고, 

10개의 트라이앵글 숫자는 아래와 같다. 

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개가 넘어가는 수 인것을 알 수 있다. 

그렇다면 5백개가 넘어가는 약수를 가진 트라이앵글 수는 몇인가? 

N = l^pm^qn^{r 으로 소인수분해되면 N의 약수의 개수는 (p+1)(q+1)(r+1)개}

#include <stdio.h> int count(int n) { int a, b, result=1; for(b=0; (n&1)==0; b++, n>>=1); result*=(b+1); for(a=3; n>=a; a+=2) { for(b=0; n%a==0; n/=a, b++); result*=(b+1); } return result; } int main() { int tri, i; for(tri=3, i=3; count(tri)<500; tri+=i++); printf("%d", tri); return 0; }