프로젝트 오일러 #69 최대 오일러의 수 비율

이번 문제는 난이도 10%의 문제입니다.

 

사실 알고보면 어려운 문제는 아니지만, 오일러의 수라는 것에 대한 이해도가 없다면, 막막하게 느낄 수 있습니다.

 

오일러의 수는 어떤 수 n에 대하여, n보다 작을 자연수 중에, n과 서로소인 수의 갯수를 말합니다.  이 수는 암호학 등에서 아주 중요하게 다루어집니다.  RSA와 같이 비대칭 키를 사용하는 암호학을 공부하고자 한다면, 오일러의 수를 이해하지 못 하면, 절대 해당 암호학을 이해할 수 없습니다.

 

대학에서 정수론이라는 과목을 들었다면 모를까, 그렇지 않다면, 배울 수 있는 기회는 별로 없죠.  (요즘은 중학생들도 이것을 아는 애들이 있습니다.  수학 올림피아드에서 가끔씩 나오는 문제이다보니.  제 경우에는 정수론 책을 하나 사서 독학을 했습니다.)

 

 

문제에서는 n에 대하여 오일러의 수 비율이 최대가 되는 수를 찾는 것입니다.  1,000,000이라는 숫자 한계가 있습니다.

 

오일러의 수는 약수의 갯수를 구하는 로직과 크게 차이는 없습니다.  약간의 변형이 필요하지만, 약수의 갯수를 구하는 로직과 비슷합니다.

 

실제 오일러의 수를 구하는 식은 다음과 같이 표현할 수 있습니다.

 

\[\varphi(n)=\prod_{p|n} (p-1)p^{d_p - 1} \]

 

식이 좀 복잡해보이겠지만, n을 나누는 모든 소수 p에 대하여, n이 p라는 소인수를 d개 가지고 있다면, (p-1)에, p의 d-1승을 계속 곱하면 그것이 오일러의 수라는 것입니다.

 

이것을 C++ 로 프로그램하면 다음과 같습니다.

 

int phi(int n)
{
    int v = 1;
    for( int i = 0 ; n > 1 && i < pcount ; i++ )
    {
        if( n%primes[i] == 0 )
        {
            v *= primes[i]-1;
            n /= primes[i];
            while( n%primes[i] == 0 ) { v *= primes[i]; n /= primes[i]; }
        }
    }
    if( n > 1 ) v *= (n-1);
    return v;
}

 

위의 함수를 이용해서 풀어도 이 문제를 풀 수는 있습니다.  그런데 저는 좀 다르게 했습니다.  어차피 소수를 구하는 것, 모든 소수에 대하여 기존에 구해진 오일러의 수 값을 가지고 최대값을 구하는 방식으로 하였습니다.

 

성능 테스트는 따로 하지 않았습니다.  하지만 아무래도 연산 오더의 차이가 있으니까요.  좀 더 나을려나요.

 

아래는 실제 제가 이 문제를 해결할 때 사용한 프로그램입니다.

 

#include <stdio.h>
#include <time.h>

int maxvalues(int primes[], int pcount, int k, int n, int phi, int *maxp)
{
    int maxv = n, maxphi = phi;
    for( int i = k ; i < pcount ; i++ )
    {
        if( n*primes[i] > 1000000 ) break;
        int u = 0;
        int c = maxvalues(primes, pcount, i+1, n*primes[i], phi*(primes[i]-1), &u);
        if( (double)c/u > (double)maxv/maxphi ) { maxv = c; maxphi = u; }
    }
    *maxp = maxphi;
    return maxv;
}

void solve1()
{
    static int primes[1000];
    int pcount = 0;
    int n = 2;

    primes[pcount++] = 3;
    for( int p = 5 ; ; p += 2 )
    {
        bool isPrime = true;
        for( int i = 0 ; primes[i]*primes[i] <= p ; i++ )
        {
            if( p%primes[i] == 0 ) { isPrime = false; break; }
        }
        if( isPrime == false ) continue;
        primes[pcount++] = p;
        n *= p;
        if( p*n > 100000000 ) break;
    }

    int maxp;
    n = maxvalues(primes, pcount, 0, 2, 1, &maxp);

    printf("Ans = %d\n", n);
}