41. 프로젝트 오일러 #41 : 팬디지털 소수

이 문제의 난이도 5%입니다.  그렇게 어렵지 않은 문제이죠.

문제를 살펴보면 다음과 같습니다.

우리는 1부터 n까지 정확하게 한번씩만 사용한 n자리 숫자가 있다면, 이것을 팬디털(pandigital) 숫자라고 부릅니다.  예를 들어서 2143은 4자리 팬디지털 숫자이면서, 또한 소수입니다.

가장 큰 n자리 팬디지털 소수는 얼마일까요?

일단 팬디지털이라는 것을 알았으면, 우리는 간단하게 1~9까지 한번만 사용해서 이 숫자를 구하면 됩니다.

팬디지털을 만들 수 있는 가장 큰 자릿수는 9자리입니다.  왜냐하면 그 이상부터는 두자리숫자가 될 수밖에 없기 때문에 팬디지털 정의에 어긋납니다.

프로그램은 9자릿수부터 만들 수 있는 모든 팬디지털수를 만듭니다.  (사실 이것을 1부터 n까지 배열하는 순열수입니다.)  순열 수 중에 사실 마지막 자릿수는 짝수 또는 5가 들어가면 안 됩니다만, 여기서는 그런 것들을 그냥 무시했습니다.

순열수를 만드는 방법은 여러가지가 있겠지만, 여기서는 간단하게 자기호출수를 이용했고, 가장 큰 수부터 차례대로 검사를 합니다.

간단하게 프로그램을 올리면 다음과 같습니다.

#include <stdio.h>
#include "isprime.h"

uint64_t TestAndReturn(uint64_t n, uint64_t m, int r, int c = 9);

int main()
{
    for( int i = 9 ; ; i-- )
    {
        uint64_t res = TestAndReturn(0, 0, i, i);
        if( res == 0 ) continue;
        printf("ans = %ju\n", res);
        break;
    }
}


uint64_t TestAndReturn(uint64_t n, uint64_t m, int r, int c)
{
    if( r == 0 )
    {
        if( isPrime(n) ) return n;
        return 0;
    }
    for( int i = c ; i > 0 ; i-- )
    {
        if( (m>>i) & 1 ) continue;
        uint64_t res = TestAndReturn(n*10+i, m|(1<<i), r-1, c);
        if( res ) return res;
    }
    return 0;
}