Project Euler - 문제 12번

Highly divisible triangular number

Problem 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?

 문제 12번 : Triangle number의 수열은 자연수를 더하여 생성된다. 그래서 7번째 Triangle number는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 될 것이다. 그리고 처음 10개의 항은 다음과 같다:

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

이제 처음 7항의 약수들을 나열해보자:

 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이 처음으로 다섯 개의 약수를 가지는 Triangle number임을 알 수 있다. 그러면 처음으로 오백개의 약수를 가지는 Triangle number는 얼마인가?

---

 이 문제의 핵심은 약수의 갯수를 구하는 방법인 것 같습니다. 일반적으로 약수의 갯수는 소인수를 통해서 바로 알 수 있습니다. 임의의 숫자 \(L\)이 소인수 \(p_i\)들로 이루어져 있다고 할 경우, 약수의 갯수 \(n\)은 다음과 같이 주어집니다.
$$
L=p_1^{n_1} \times p_2^{n_2} \times \cdots \quad \Rightarrow \quad n=(n_1 + 1) \times (n_2+1) \times \cdots
$$
그러면 소인수분해를 한 뒤에 약수의 갯수를 위와 같이 구하는 코드를 작성하면 됩니다.

int num_div(int n)
{
 int num_cal = 1;
 int temp = 0;
 
    while(n%2 == 0)
    {
        n = n/2;
        temp++;
 }
    num_cal *= temp+1;

    for(int k = 3; k < sqrt(n); k += 2)
    {
  temp = 0;
     while(n%k == 0)
     {
      n = n/k;
      temp++;
     }
     num_cal *= temp+1;
     
     if(n == 1)
      break;
    }
    if(n != 1)
     num_cal *= 2;
     
    return num_cal;
}

 이처럼 소인수분해를 하여 바로 약수의 갯수를 리턴하는 함수를 이용하여 약수의 갯수가 500개를 최초로 넘어가는 숫자를 찾으면 결과는 아래와 같이 나타납니다.