[C/C++] 프로젝트 오일러 #12 Highly Divisible Triangular Number

 

삼각수(triangular number)는 다음과 같이 자연수를 차례대로 더한 값으로 정의됩니다.

\[ T_n = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} \]

예를 들어, 처음 7개의 삼각수는 다음과 같습니다:

1, 3, 6, 10, 15, 21, 28

이 문제에서는, 500개 이상의 약수를 가지는 첫 번째 삼각수를 찾는 것이 목표입니다.

 

triangular number

 

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #12 - Highly Divisible Triangular Number
//        - by Aubrey Choi
//        - created at 2014-12-29
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

#define    NUM    500

int GetNumDivisors(int n);

int solve1()
{
    int n = NUM;
    int a, b;

    b = GetNumDivisors(n++/2);
    for( ; ; )
    {
        a = GetNumDivisors(n++);
        if( a*b > NUM ) break;
        b = GetNumDivisors(n++/2);
        if( a*b > NUM ) break;
    }

    printf("Ans = %d\n", (n-2)*(n-1)/2);
}

int GetNumDivisors(int n)
{
    int c = 1;
    int k;

    for( k = 0 ; !(n%2) ; k++ ) n /= 2;
    c = k+1;
    for( int p = 3 ; p*p <= n ; p+=2 )
    {
        for( k = 0 ; !(n%p) ; k++ ) n /= p;
        c *= k+1;
    }
    return c*((n > 1)+1);
}

int main()
{
    clock_t t;

    t = clock();
    solve1();
    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

    return 0;
}

 

1. #include 헤더
• stdio.h, stdlib.h, string.h, stdint.h, time.h, math.h는 각각 표준 입출력, 수학 함수, 시간 측정 등을 위해 사용됩니다.

 

2. 매크로 정의

#define NUM 500

• NUM은 문제 조건인 약수 개수 500을 나타냅니다.

3. GetNumDivisors 함수
• 특정 숫자의 약수 개수를 계산합니다.

int GetNumDivisors(int n)

• 약수 개수를 구하기 위해 소인수 분해를 사용합니다:
• 2로 나누어지는 횟수를 카운트하여 을 구함.
• 그 이후 홀수 소인수들을 순회하며  값을 누적 곱.
• 남은 값이 1보다 크면 소수로 간주하고 에 추가 곱셈.

4. solve1 함수
• 문제 해결의 핵심 로직.

int solve1()

• 삼각수 \(T_n\)의 성질을 활용:
• 삼각수  \( T_n = \frac{n(n+1)}{2} \)의 약수 개수는 n과 n+1 각각의 약수 개수에 의존.
• n이 홀수일 때, n과 (n+1)/2의 약수를 계산.
• n이 짝수일 때, n/2와 n+1의 약수를 계산.
• 조건 a * b > NUM을 만족하는 삼각수를 찾으면 종료.