500. 프로젝트 오일러 #500 : 약수의 갯수가 2의 500500승인 최소수 찾기

이번 문제는 알고리즘이 관건인 문제인지라,

일단 모든 수를 찾아서 가장 작은 수를 찾는 것은 쉽지 않습니다.  왜냐하면, 우리가 상상할 수 없을 정도로 큰 수가 나오니까요.

그리고 소인수분해를 하는 것도 쉽지 않죠.  소인수분해는 알고리즘 상 현재까지는 가장 진보된 알고리즘이라고 할 수 있는 것이 나와있지 않은 상태입니다.

소인수분해가 적절한 시간 (설사 며칠이 걸리더라도) 안에 풀 수 있다면, 지금의 공인 인증서를 비롯하여 많은 암호 체제가 모두 무용지물이 됩니다.

비대칭키 암호 알고리즘의 핵심은 소인수분해가 어렵다는 것을 토대로 하고 있습니다.  1000비트짜리 암호키를 가지는 비대칭키라고 한다면, 두개의 소수는 각각 500비트정도를 고르게 됩니다.  500비트라면, 10의 150승정도가 되죠.  즉, 그 근처의 소수를 찾는 것조차도 적절한 시간안에 찾는 것이 어려울 정도죠.  그러니 소인수분해는 더더욱 말할 것 없습니다.

이번 문제는 2의 500500승만큼의 약수를 가지는 최소수를 찾는 것이죠.

예를 들자면, 2의 5승만큼의 약수를 가지는 최소수를 찾기 위해서는, 서로 다른 소수가 가 있을 때, 다음과 같은 경우에 2의 5승만큼의 약수를 가집니다.

이 답을 풀기 위해서 다음과 같이 했습니다.

d : 약수 갯수의 승수.

GetMinNumber( d )

  F <- {}

  while( d > 0 )

    c <- minimum element of P

    if F = {} or c < minimum elemement of F then

       F <- { (c, c) } U F

       P <- P - c

    else

       r <- minimum element of F

       F <- F - r

       F <- { ( r.x*r.x*r.y, r.y ) } U F

   d <- d - 1

  result <- 1

  for each c in F

    result <- result * c.x

이런 알고리즘을 가지면, 우리는 최소의 수를 구할 수 있습니다.

2의 5승 약수갯수를 가지는 수를 찾는다면,

F 는 현재 비어있으므로 가장 작은 소수 2를 넣습니다.

F : (2, 2)

그 다음 소수는 3이므로, 3과 2x2와 비교합니다.  3이 작으므로 3을 넣습니다.

F : (2, 2) (3, 3)

그 다음 소수는 5이므로, 5와 2x2와 비교합니다.  2x2가 작으므로, (2x2x2, 2)를 (2, 2) 대신 넣습니다.

F : (3, 3) (8, 2)

역시 그 다음 소수는 5이므로 5와 3x3을 비교합니다.  5가 작으므로 5를 넣습니다.

F : (3, 3) (8, 2) (5, 5)

다음 소수는 7이므로 7과 3x3을 비교합니다.  7이 작으므로 7을 넣으면,

F : (3, 3) (8, 2) (5, 5) (7, 7)

이 되어서 F의 모든 원소들의 첫번째 값을 곱하면,

3x8x5x7 = 840

이 되어, 840이 최소값이 됩니다.

이것을 프로그램적으로 기술하기 위해서 삽입정렬을 사용했습니다.  아마도 힙을 사용했으면 더 빠른 시간안에 답을 찾을 수 있었겠더라고요.

소스는 다음과 같습니다.

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

#define DIV     500500507
#define TDIVS   500500

struct Factor
{
    uint64_t value;
    uint32_t prime;
    uint32_t power;
};

bool IsPrime(uint64_t n);
void Insert(uint32_t k);
bool CheckAndSquareMove(uint32_t k);

Factor factors[TDIVS];
int pfactors = 0;

int main()
{
    uint32_t cp = 3;

    int cpp = 1;

    Insert(2);

    int pvalue = TDIVS - 1;
    while( pvalue-- > 0 )
    {
        if( !CheckAndSquareMove(cp) )
        {
            Insert(cp);
            for( cp += 2 ; !IsPrime(cp) ; cp += 2 ) ;
        }
    }
    uint64_t ans = 1;
    for( int i = 0 ; i < pfactors ; i++ )
    {
        ans *= (factors[i].value%DIV);
        ans %= DIV;
    }
    printf("ans = %jd\n", ans);
}

void Insert(uint32_t k)
{
    int last = pfactors++ - 1;
    uint64_t v = k; v *= k;
    while( last >= 0 && v < factors[last].value*factors[last].prime )
    {
        factors[last+1] = factors[last];
        last--;
    }
    factors[last+1].value = k;
    factors[last+1].prime = k;
    factors[last+1].power = 1;
}

bool CheckAndSquareMove(uint32_t k)
{
    uint64_t value = factors[0].value * factors[0].prime;
    if( value > k ) return false;
    Factor t;
    t.value = factors[0].value * value;
    t.prime = factors[0].prime;
    t.power = factors[0].power+1;
    int last = 1;
    while( last < pfactors &&
        t.value*t.prime > factors[last].value*factors[last].prime )
    {
        factors[last-1] = factors[last];
        last++;
    }
    factors[last-1] = t;
    return true;
}

아울러 여기서 소수를 찾기 위해서 소수인지 검사하는 것은 밀러 라빈 방법을 사용하였습니다.