3. 삼각수의 약수의 개수


문제 중에 처음 호기심을 자극한 문제가 이것이다.

이 문제는 언뜻 보면 기초적인 문제 같지만, 동작 성능을 고려하면 상당히 고난이도 문제다.


물론, 단순무식하게 아래와 같이 만들어도 동작은 한다…


#include <stdio.h>
#include <stdlib.h>

int countOfDivisors(int num)
{
    if (num < 2) return 1;

    // 1과 자신은 무조건 약수이므로 2부터 시작
    int ret = 2;
    for (int i = num / 2; i >= 2; i--) {
        if (num % i == 0) ret++;
    }
    return ret;
}

int main(int argc, char* argv[])
{
    printf("-= count of divisors of triangular numbers =-\n");

    int triangularnumber = 0;
    int n = 1;
    while (true) {
        triangularnumber += (n++);
        int count = countOfDivisors(triangularnumber);
       
        if (count >= 500) {
            printf("sum of 1..%d = %d\n", n - 1, triangularnumber);
            printf("count of dividors of %d = %d\n", triangularnumber, count);

            break;
        }
    }
    return 0;
}


위 코드에서는 약수의 개수를 세는 함수에 아주 최소한의 최적화만 했다.

물론, 이렇게 만들어도 동작은 아무 이상 없이 한다. 조금 느릴 뿐이다.

내 컴퓨터(AMD A8-8870 3GHz)에서 44분 16초 걸렸다…



이건 좀 너무한 것 같으니, 살짝 최적화를 해보기로 한다.

중학교 때쯤 소인수분해라는 걸 배우는데. 여기서 우리는


d = a^m \cdot b^n \cdot c^o


형태로 인수분해되는 d의 약수의 개수는 아래와 같다는 것을 배웠다.


(m+1) \cdot (n+1) \cdot (o+1)


그렇다면, 일단 2로 몇번 나눌 수 있는 지를 확인한 뒤에 그 부분만 적용해보기로 한다.


#include <stdio.h>
#include <stdlib.h>

int countOfDivisors(int num)
{
    // a^n*b^m 으로 소인수분해되는 수의 약수 갯수는
    // (n+1)*(m+1)임
    // 2^n 쪽은 쉽게 계산 가능함
    int two = 0;
    while ((num & 1) == 0) {
        num >>= 1;
        two++;
    }

    int ret;
    if (num < 2) ret = 1;
    else {
        ret = 2;
        for (int i = num / 2; i >= 2; i--) {
            if (num % i == 0) ret++;
        }
    }
    return ret*(two + 1);
}

int main(int argc, char* argv[])
{
    printf("-= count of divisors of triangular numbers =-\n");

    int triangularnumber = 0;
    int n = 1;
    while (true) {
        triangularnumber += (n++);
        int count = countOfDivisors(triangularnumber);
       
        if (count >= 500) {
            printf("sum of 1..%d = %d\n", n - 1, triangularnumber);
            printf("count of dividors of %d = %d\n", triangularnumber, count);

            break;
        }
    }
    return 0;
}


단지 약수 중에 2에 대해서만 최적화했을 뿐인데, 조금 빨라졌다.

29분 17로 34% 정도 빨라진 것이다.


그렇다면, 아예 소인수분해의 개념을 제대로 적용해보기로 한다.

단, 모든 약수를 다 뽑아내는 것이 아니라 약수의 개수만 세는 것이라 약수 자체를 뽑아낼 필요는 없다.


#include <stdio.h>
#include <stdlib.h>

int countOfDivisors(int num)
{
    if (num < 2) return 1;
    int half = num / 2;
    int ret = 1;

    for (int i = 2; i <= half; i++) {
        int now = 0;
        while (num % i == 0) {
            now++;
            num /= i;
        }
        if (now) {
            ret *= (now + 1);
            half = num / 2;
        }
    }

    if (num > 1) {
        ret *= 2;
    }

    return ret;
}

int main(int argc, char* argv[])
{
    printf("-= count of divisors of triangular numbers =-\n");

    int triangularnumber = 0;
    int n = 1;
    while (true) {
        triangularnumber += (n++);
        int count = countOfDivisors(triangularnumber);
       
        if (count >= 500) {
            printf("sum of 1..%d = %d\n", n - 1, triangularnumber);
            printf("count of dividors of %d = %d\n", triangularnumber, count);

            break;
        }
    }
    return 0;
}


이렇게 최적화된 결과는 소요 시간이 ms 단위로 나온다.

제대로 최적화된 것이다.


-= count of divisors of triangular numbers =-
sum of 1..12375 = 76576500
count of dividors of 76576500 = 576


덧. 이 문제는 이 회사에서 창작한 오리지널 문제가 전혀 아니다.

프로젝트 오일러 12번 문제를 그대로 출제한 것이다.



  1. bumsook 2014.10.13 11:52

    프로젝트 오일러 문제가 입사 테스트로 나온다니 신기하네요.

    저 문제를 프로젝트 오일러에서 봤을때 저같은경우 최적화를 "1~sqrt(n)까지 약수를 세되, sqrt(n)이 아닌 값들에선 2씩 증가시킨다 (d와 n/d를 한번에 세 주는 식으로)" 했었는데 어떤 쪽이 더 빠른지 문득 궁금하네요. 이것도 사실 n까지 셀걸 sqrt(n)까지 세는거니 상당히 빠른 코드긴 하겠지만 그래도 소인수분해 optimization쪽이 정말 큰 숫자들에 대해서는 더 빠를 것 같기도 하구요. Java에서 저 sqrt(n) optimization으로 400ms쯤 걸리던데 소인수분해는 얼마나 걸리나요?

+ Recent posts