[C/C++] 프로젝트 오일러 #41 : 팬디지털 소수

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

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

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

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

---

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

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

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

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

 

pandigital numbers

---

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

//------------------------------------------------
//    Project Euler #41 - Pandigital Prime
//        - by Aubrey Choi
//        - created at 2015-03-27
//------------------------------------------------
#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;
}

이 프로그램은 Project Euler 문제 #41 - 판디지털 소수(Pandigital Prime) 를 해결하기 위한 코드입니다.
가장 큰 n-자리 판디지털 소수를 찾기 위해 순열을 생성하고, 그중 소수인 가장 큰 수를 반환합니다.

 

코드 구조 및 설명
1. main() 함수
• i 값을 9부터 시작하여 1씩 감소시키면서 TestAndReturn() 함수를 호출합니다.
• TestAndReturn() 함수가 0이 아닌 값을 반환하면, 해당 값을 출력하고 프로그램을 종료합니다.
2. TestAndReturn(uint64_t n, uint64_t m, int r, int c) 함수
• 재귀적으로 n을 구성하면서 판디지털 숫자를 생성하는 함수입니다.
• r == 0일 때 n이 소수인지 검사하여 소수이면 반환합니다.
• for문을 이용하여 c부터 1까지 반복하며 가능한 숫자를 선택합니다.
• m은 비트마스크를 이용하여 현재까지 사용한 숫자를 추적합니다.
• res가 0이 아니면 최종적으로 해당 값을 반환합니다.

 

핵심 로직
1. TestAndReturn() 함수는 9부터 시작하여 가능한 모든 판디지털 숫자를 생성합니다.
2. 가장 큰 숫자부터 검사하며, 처음 발견한 소수를 즉시 반환하여 가장 큰 소수를 찾습니다.
3. isPrime() 함수를 사용하여 소수 여부를 확인합니다.
4. 비트마스크(m|(1<<i))를 활용하여 중복된 숫자가 사용되지 않도록 합니다.

 

예상 실행 흐름
1. i = 9부터 TestAndReturn(0, 0, 9, 9) 호출
2. 9자리 판디지털 숫자를 가장 큰 숫자부터 생성
3. 소수 여부 검사 후, 가장 큰 소수 발견 시 즉시 반환
4. 정답 출력 후 종료