37. 프로젝트 오일러 : 잘라도 소수가 되는 소수

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

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

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

원래라면, 모든 소수를 다 찾고, 모든 소수에 대해서 잘라가면서 소수인지 검사하면 되는 간단한 프로그램이 됩니다.  소수를 검사하기 위해서 소수를 다 찾고, 이진 검색을 이용해서 소수인지 검사하면 편하지만, 제가 중점을 둔 것은 이러한 소수의 성질이었습니다.

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

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

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

#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;
}