51. 프로젝트 오일러 #51 : 소수 자릿수 대치

프로젝트 오일러 #51 문제는 처음으로 난이도 5%가 아닌 문제입니다.

다른 문제들에 비해서 난이도가 좀 있습니다.

주어진 문제는 56xx3 과 같은 x로 비어진 숫자가 있는데, 이 x에 0~9까지 숫자를 넣었을 때, 소수는 몇개가 나오는 가입니다.

56003, 56113, 56223, 56333, 56443, 56553, 56663, 56773, 56883, 56993 이라는 10개의 숫자들을 만들 수가 있는데요.  이 중 소수는 7개나 됩니다.  이 때, 56003(이 그룹 중 가장 작은 수)는 소수가 7개가 되는 최소의 수입니다.

찾아야 하는 수는 소수가 8개가 되는 최소의 수입니다.

문제를 적용하는 방법을 구상하는 것이 어렵지, 문제 자체는 짧은 시간에 컴퓨터가 계산해냈습니다.

저는 기본적으로 자기호출(recursion) 방법을 사용했습니다.  모든 경우의 수를 만들어 나갈 때, 편하게 사용할 수 있는 방법이 자기 호출 방법인 듯 합니다.

자릿수는 그리 많지 않은 문제라고 생각했죠.

일단, 7개 중 최소의 자릿수가 5자릿수이므로, 5자릿수부터 시작해서 한자리씩 늘려갔습니다.  그리고 속도를 빠르게 하기 위해서 마지막 자리는 (1, 3, 7, 9)로 끝나는 것만 생각했습니다.  

변수를 digit, mask, count 라는 것을 두고, 각각이 푸는데 역할을 두고 있습니다.

digit은 자릿수입니다.  6개의 숫자를 쓰면, digit은 6이 됩니다.  mask는 빈 공간이 됩니다.  빈 공간의 갯수는 1부터 자릿수-1만큼 갈 수 있습니다.  (왜냐하면 마지막 자릿수는 1, 3, 7, 9 중에 하나여야하기 때문입니다.)  빈공간과 자리가 마련되었으면, count 변수를 이용해서 소수가 되는 횟수를 잽니다.  이 횟수가 8이 되면, 우리가 원하는 답을 찾게 됩니다.

다음은 제가 작성한 코드입니다.

코드는 참고용으로만 봐주세요.

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

#define TARGET  8

int FindDigit(int digit, int holes, int mask, int s);
int GetPrimeFamily(int c, int digit, int n, int mask);

int main()
{
    for( int digit = 5 ; digit < 7; digit++ )
    {
        for( int holes = 1 ; holes < digit ; holes++ )
        {
            int v = FindDigit(digit, holes, 0, 1);
            if( v ) { printf("Ans = %d\n", v); return 0; }
        }
    }
}

int FindDigit(int digit, int holes, int mask, int s)
{
    if( holes == 0 )
    {
        const int s[4] = { 1, 3, 7, 9 };
        for( int i = 0 ; i < 4 ; i++ )
        {
            int v = GetPrimeFamily( 1, digit, s[i], mask );
            if( v ) return v;
        }
        return 0;
    }

    //  Make holes
    for( int i = s ; i <= digit-holes ; i++ )
    {
        int v = FindDigit(digit, holes-1, mask | (1<<i), i+1);
        if( v ) return v;
    }
    return 0;
}

int GetPrimeFamily(int c, int digit, int n, int mask)
{
    if( c == digit )
    {
        int s = 10, m = 0, count = 0;
        for( int i = 1 ; i < digit ; i++, s *= 10 ) if( (mask>>i)&1 ) m += s;
        if( !(mask>>(digit-1)) && n*10/s == 0 ) return 0;
        int start = (mask>>(digit-1));
        for( int i = start ; i < 10 ; i++ )
            if( isPrime(n+i*m) ) count++;
        if( count < TARGET ) return 0;
        printf("digit = %d, n = %d, mask = %X, count = %d\n", digit, n, mask, count);
        for( int i = start ; i < 10 ; i++ )
            if( isPrime(n+i*m) ) printf("%d ", n+i*m);
        putchar('\n');
        for( int i = start ; i < 10 ; i++ )
            if( isPrime(n+i*m) ) return n+i*m;
    }

    if( (mask>>c)&1 ) return GetPrimeFamily(c+1, digit, n, mask);
    int t = 1;
    for( int i = 0 ; i < c ; i++, t *= 10 );
    for( int k = 0 ; k < 10*t ; k += t )
    {
        int v = GetPrimeFamily(c+1, digit, n+k, mask);
        if( v ) return v;
    }
    return 0;
}