[C/C++] 프로젝트 오일러 #108 Diophantine Reciprocals I(소인수분해)

프로젝트 오일러 문제 #108: Diophantine Reciprocals I는 다음과 같은 문제입니다:

이 문제는 다음과 같은 형태의 Diophantine 방정식을 다룹니다:
\[ \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \]

 

여기서 x, y, n은 모두 양의 정수입니다. 위 식을 변형하면:
\[ (x - n)(y - n) = n^2 \]

이 방정식의 해 (x, y)의 개수를 세는 것이 문제의 핵심입니다. 특히, 이 문제는 주어진 n에 대해 위 식을 만족하는 서로 다른 해 쌍의 개수가 1000개 이상이 되는 가장 작은 n을 찾는 것입니다.

해의 개수를 셀 때 (x, y) 와 (y, x)는 같은 해로 간주되므로, 해의 개수를 정확히 세는 것이 중요합니다.

요약하면, 양의 정수 n 중에서 위의 방정식을 만족하는 서로 다른 해 쌍의 개수가 1000 이상인 가장 작은 n을 구하는 문제입니다.

 

문제는 복잡해보이지만, 사실 간단합니다.  가장 중요한 것은 \(n^2\) 약수의 개수가 몇개인가이죠.  예를 들어서 n = 10 이라면, n은 \( 2^1 \times 5^1 \) 으로 표기 됩니다.  n의 약수의 개수는 총 4개이지만, \(n^2\)의 약수의 개수는 9개가 되겠죠.  그러면 쌍은 (1, 100), (2, 50), ..., (10, 10) 으로 5개가 나옵니다.  실제 x, y 해는 n을 더한 (11, 110), (12, 60), ..., (20, 20)이 됩니다.

 

math equation

 

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #108 - Diophantine Reciprocals I
//        - by Aubrey Choi
//        - created at 2015-11-02
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

int GetCount(int n)
{
    int count = 1;
    if( n%2 == 0 )
    {
        int lc = 0;
        while( n%2 == 0 )  { lc++; n/=2; }
        count *= lc*2+1;
    }
    for( int p = 3 ; p*p <= n ; p += 2 )
    {
        if( n%p ) continue;
        int lc = 0;
        while( n%p == 0 ) { lc++; n/=p; }
        count *= lc*2+1;
    }
    if( n > 1 ) count *= 3;
    return (count+1)/2;
}

void solve1()
{
    for( int n = 1000 ; ; n++ )
    {
        int count = GetCount(n);
        if( count > 1000 )
        {
            printf("Ans = %d (%d)\n", n, count);
            break;
        }
    }
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

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

 

1. GetCount 함수

• 입력으로 숫자를 받아 가능한 해의 개수를 계산하는 함수.
• 숫자를 소인수 분해하며, 각 소인수의 지수를 활용해 해의 개수를 계산.
• 최종적으로 계산된 해의 개수를 대칭성을 고려해 절반으로 나눔.

2. solve1 함수

• 1000부터 시작해 가능한 숫자를 하나씩 증가시키며 조건을 만족하는 숫자를 찾음.
• GetCount를 호출해 현재 숫자에 대한 해의 개수를 확인.
• 해의 개수가 1000을 초과하면 해당 숫자를 출력하고 반복을 종료.

3. main 함수

• solve1을 호출해 문제를 해결.
• 프로그램의 실행 시간을 측정하여 성능을 확인.