[C/C++] 프로젝트 오일러 #37 잘라도 소수가 되는 소수

Truncatable Prime은 소수 중에서도 매우 특별한 성질을 가진 숫자입니다. 이 숫자는 왼쪽에서부터 자릿수를 하나씩 제거하거나, 오른쪽에서부터 자릿수를 하나씩 제거했을 때 남는 모든 숫자가 여전히 소수로 유지되는 특성을 가집니다. 예를 들어, 일반적인 소수는 1과 자기 자신으로만 나누어떨어지지만, Truncatable Prime은 단순히 소수일 뿐만 아니라, 자릿수를 제거한 모든 숫자 또한 소수라는 추가적인 조건을 만족해야 합니다. 이러한 점에서 Truncatable Prime은 일반적인 소수보다 훨씬 희소하고 독특한 성격을 띠게 됩니다.

 

예를 들어, 숫자 3797은 Truncatable Prime의 좋은 사례입니다. 이 숫자를 왼쪽에서부터 하나씩 자르면 379, 37, 3이 되며, 오른쪽에서부터 자르면 797, 97, 7이 됩니다. 이 모든 숫자가 소수라는 점에서 3797은 Truncatable Prime 조건을 완벽히 충족합니다. 반면, 단순히 한 자릿수의 소수(예: 2, 3, 5, 7)는 자릿수를 제거할 여지가 없으므로 Truncatable Prime으로 간주되지 않습니다. 따라서 Truncatable Prime은 최소 두 자릿수 이상이어야 하며, 자릿수를 제거하는 과정을 통해 소수성을 유지해야 합니다.

 

문제에서 요구하는 것은 이러한 Truncatable Prime을 모두 찾아내는 것입니다. 이때 Truncatable Prime의 수는 유한하며, 적절한 범위를 설정하여 탐색을 수행해야 합니다. 최종적으로 모든 Truncatable Prime을 찾은 뒤, 그 숫자들의 합을 계산하는 것이 문제의 핵심입니다. 이 과정에서 효율적인 소수 판별 알고리즘과 반복적인 검증 절차가 필요하며, 문제를 해결하기 위해 정확성과 성능을 동시에 고려해야 합니다.

 

난이도는 5%로 낮은 난이도의 문제입니다.

이 문제는 앞을 잘라도 소수가 되는 소수를 찾아야 합니다.

예를 들면 3797은 자체로 소수이지만, 797, 97, 7 도 소수이며, 반대로 379, 37, 3도 소수가 됩니다.

원래라면, 모든 소수를 다 찾고, 모든 소수에 대해서 잘라가면서 소수인지 검사하면 되는 간단한 프로그램이 됩니다. 소수를 검사하기 위해서

 

소수를 다 찾고, 이진 검색을 이용해서 소수인지 검사하면 편하지만, 제가 중점을 둔 것은 이러한 소수의 성질이었습니다.

두자릿수 이상의 수중, 마지막 자리가 5라면 그 수는 반드시 5로 나누어지기 때문에 소수가 될 수 없습니다. 또한 첫 숫자가 9이거나 마지막 숫자가 9라면, 잘라내기에 의해서 9가 남기때문에 첫 숫자와 마지막 숫자는 9가 될 수 없습니다. 1도 마찬가지이고, 5도 마찬가지이므로, 홀수중에서는 3과 7만이 첫 숫자와 마지막 숫자가 될 수 있습니다.

 

그리고 원래대로라면, 완료 조건을 좀 세워서 프로그램을 해야하지만, 문제에서 이러한 소수는 11개밖에 안 된다고 했기 때문에, 저는 편하게 11개만 찾기로 했습니다.

 

truncatable primes

 

그래서 만들어진 프로그램은 다음과 같습니다. 다소 복잡하게 프로그램이 작성되었네요.

//------------------------------------------------
//    Project Euler #37 - Truncatable Primes
//        - by Aubrey Choi
//        - created at 2015-03-21
//------------------------------------------------
#include <stdio.h>

bool IsOddPrime(int p);
void Push(int tp[][2], int &t, int v, int e);
void Pop(int tp[][2], int &h, int *v, int *e);

int main()
{
    int tp[1000000][2];
    int h = 0, t = 0;

    Push(tp, t, 3, 10);
    Push(tp, t, 7, 10);

    int ans = 0;
    int count = 0;
    while( count < 11 )
    {
        int s[] = { 2, 3, 5, 7 };
        int p[] = { 1, 3, 7, 9 };
        int v, e;
        Pop(tp, h, &v, &e);
        for( int i = 0 ; i < 4 ; i++ )
        {
            int t = s[i]*e + v;
            int u;
            for( u = t ; u > 10 ; u /= 10 )
                if( IsOddPrime(u) == false ) break;
            if( u > 10 ) continue;
            ans += t;
            count++;
        }
        for( int i = 0 ; i < 4 ; i++ )
        {
            if( IsOddPrime(p[i]*e+v) == false ) continue;
            Push(tp, t, p[i]*e+v, e*10);
        }
    }
    printf("ans = %d\n", ans);
}

void Push(int tp[][2], int &t, int v, int e)
{
    tp[t][0] = v;
    tp[t][1] = e;
    t = (t+1)%1000000;
}

void Pop(int tp[][2], int &h, int *v, int *e)
{
    *v = tp[h][0];
    *e = tp[h][1];
    h = (h+1)%1000000;
}

bool IsOddPrime(int p)
{
    for( int i = 3 ; i*i <= p ; i+=2 )
        if( p%i == 0 ) return false;
    return true;
}