[Project Euler #12][C++] 500개 이상의 약수를 갖는 가장 작은 삼각수는?

문제12 : 500개 이상의 약수를 갖는 가장 작은 삼각수는?

문제

1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다.
예를 들어 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

위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다.

그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까?

문제 해결 방법

• 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하려고 했으나 시간이 너무 오래 걸려서 포기하였다.

  • int checkCommonDivisor(int n)

• 그래서 빠르게 숫자의 약수의 개수를 구하는 알고리즘(참고) 를 사용하여 빠른 시간에 문제를 해결하였다.

  • int countDivisors(int n)
    • for 문을 돌려서 약수의 개수를 구하려는 수(n)를 1부터 구하려는 수의 제곱근(sqrt(n))까지의 수와 나머지를 구하는 연산을 반복 수행한다.
      • n을 1부터 n까지의 수가 아닌, 1부터 n의 제곱근 까지의 수와 나누어 시간을 절약하기 위한 방법이다.
      • 나머지가 0일 경우, (나누어 떨어질 경우) (n % i == 0)
        • 두 가지의 경우로 나누어 카운트(count) 값을 증가시킨다.
          • 첫 번째, n / i == i일 경우, (즉, 16 / 4 == 4일 경우) 카운트(count) 값을 1 증가시킨다.
            • 4 x 4 = 16
          • 두 번째, n / i != i일 경우, (즉, 16 / 2 != 2일 경우) 카운트(count) 값을 2 증가시킨다.
            • 2 x 8 = 16
            • 8 x 2 = 16
  • 이 방법을 사용하면 다음과 같은 연산이 수행된다.

  n = 16
  1, 2, 4, 8, 16
  
  sqrt(n) = 4
  1, 2, 4
  ↓↓ ↓
  2  2  1  => 약수의 개수는 총 5개
  -------
  1  2  4
  16 8  4
  

• 약수의 개수를 구하는 함수를 작성한 후, 삼각수(Triangular Number) 를 하나하나씩 생성하여 약수의 개수를 구하는 함수의 인자로 넣어준 후, 그 값이 N(=500) 이상일 경우 무한 반복문을 종료하도록 하였다.

• 그리고 최종적으로 triNum 값이 출력되도록 하였다.

소스 코드

#include <iostream>
#include <cmath>
using namespace std;
 
#define N 500
 
int checkCommonDivisor(int n) {                                                                                 
    int count = 0;
    for (register int i = 1; i <= n; i++) {
        if (n % i == 0) {
            count++;
        }
    }
    return count;
}
 
// O(n^1/3)
int countDivisors(int n) {
    int count = 0;
    for (register int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            // If divisors are equal,
            // count only one
            if (n / i == i) {
                count++;
            }
            else {  // Otherwise count both
                count = count + 2;
            }
        }
    }
    return count;
}
 
int main() {
    int cnt = 0, n = 1, triNum = 0;
    
    while (1) {
        for (register int i = 1; i <= n; i++) {
            triNum += i;
        }
        cnt = countDivisors(triNum);
        // cout << triNum << ": " << cnt << endl;
        if (cnt >= N) {
            break;
        }
        n++;
        triNum = 0;
    }
    
    cout << triNum << endl;
 
    return 0;
}

정답

76576500

심화 공부

삼각수(Triangular Number)

1부터 시작하는 연속된 자연수의 합을 나타내는 수로 처음 몇 삼각수는 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, ... 이다. 삼각수는 다음 공식으로 구할 수 있다.

$$ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} = \frac{n^2 + n}{2} = \binom {n+1}{2} $$

일화에 의하면, *카를 프리드리히 가우스* 는 10살 때 1부터 100까지의 자연수를 모두 더하라는 선생님의 말을 듣고, 이러한 합을 1+100, 2+99와 같이 합이 101이 되는 50쌍의 수의 합으로 전환하여 5050임을 구하였다.

약수 함수(Divisor Function)

자연수 $n$의 약수의 개수, 약수의 합 등 약수의 $x$거듭제곱의 합을 약수 함수 $\sigma _{x}(n)$라 한다. 즉, $\sigma _{x}(n)=\sum _{d\mid n}d^{x} $이고, 여기서 $d\mid n$는 $n$의 약수 $d$ 표시이다.

$n$을 소인수 분해한 결과가 $\prod _{i=1}^r p_i^{a_i}$일 때, 약수 함수는 다음과 같다.

$$ \sigma _{x}(n)=\prod _{i=1}^{r}\sum _{j=0}^{a_{i}}p_{i}^{jx}=\prod _{i=1}^{r}\left(1+p_{i}^{x}+p_{i}^{2x}+\cdots +p_{i}^{a_{i}x}\right)$$

x ≠ 0일 때는 아래처럼 조금 단순하게 표시할 수 있다:

$$ \sigma _{x}(n)=\prod _{i=1}^{r}{\frac {p_{i}^{(a_{i}+1)x}-1}{p_{i}^{x}-1}}$$

x = 0일 때는 아래처럼 더 단순하고, 이는 약수의 개수를 나타내고 $\tau(n)$또는 $d(n)$으로도 표기한다:

$$ \sigma _{0}(n)=\prod _{i=1}^{r}(a_{i}+1)$$

---

문제 출처 : https://euler.synap.co.kr/problem=12