49. 프로젝트 오일러 #49 : 소수 순열

이 문제는 좀 복잡해보이기는 하지만, 실제 풀이과정은 단순한 문제입니다.

세개의 4자리 숫자는 숫자들의 순서만 다르면서 소수인 숫자들입니다.  

예를 들어서 1487, 4817, 8147 세 숫자는 1, 4, 7, 8 의 4개의 숫자들을 순서만 달리하면서, 각각이 소수인 숫자들입니다.

이러한 조건을 만족하는 또다른 숫자 조합을 찾으라는 것이 이 문제입니다.  (실제 모든 경우를 해도, 4자리 숫자는 예를 든 것과 여기서 원하는 답, 이렇게 두가지밖에 없습니다.)

다음 그림은 프로젝트 오일러 사이트에 있는 문제입니다.

알고리즘을 작성할 때, 4자리로 만드는 순열을 어떻게 만들것인가가 가장 중요했습니다.  모든 경우를 다 찾아봐도 되겠지만, 그러면 경우의 수가 너무 많아집니다.  그래서 제 경우에는 4개의 숫자를 고르고, 그 숫자들을 이용해서 순열을 구해서, 그것을 이용해서 소수인지 검사하는 방법을 이용했습니다.  4자리 숫자에 대한 순열 경우의 수는 4! 로 24가지밖에 안됩니다.  

그래서 제가 작성한 코드는 다음과 같습니다.

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

void TestAndDisplay(int n[], int s, int d);
int main()
{
    int n[4];
    TestAndDisplay(n, 0, 0);
}

void TestAndDisplay(int n[], int s, int d)
{
    int perm[][4] =
    {
        { 0, 1, 2, 3 }, { 0, 1, 3, 2 }, { 0, 2, 1, 3 }, { 0, 2, 3, 1 },
        { 0, 3, 1, 2 }, { 0, 3, 2, 1 }, { 1, 0, 2, 3 }, { 1, 0, 3, 2 },
        { 1, 2, 0, 3 }, { 1, 2, 3, 0 }, { 1, 3, 0, 2 }, { 1, 3, 2, 0 },
        { 2, 0, 1, 3 }, { 2, 0, 3, 1 }, { 2, 1, 0, 3 }, { 2, 1, 3, 0 },
        { 2, 3, 0, 1 }, { 2, 3, 1, 0 }, { 3, 0, 1, 2 }, { 3, 0, 2, 1 },
        { 3, 1, 0, 2 }, { 3, 1, 2, 0 }, { 3, 2, 0, 1 }, { 3, 2, 1, 0 }
    };
    if( d == 4 )
    {
        int m[24], count = 0;
        for( int i = 0 ; i < 24 ; i++ )
        {
            int q = 0;
            for( int j = 0 ; j < 4 ; j++ ) { q*=10; q+=n[perm[i][j]]; }
            for( int j = 0 ; j < count ; j++ )
                if( q == m[j] ) { q = 0; break; }
            if( q > 1000 && isPrime(q) ) m[count++] = q;
        }
        if( count < 3 ) return;
        for( int i = 0 ; i < count-2 ; i++ )
        {
            for( int j = i+1 ; j < count-1 ; j++ )
            {
                int cd = m[j]-m[i];
                for( int k = j+1 ; k < count ; k++ )
                {
                    if( m[k] != m[j]+cd ) continue;
                    printf("%04d%04d%04d cd = %d\n", m[i], m[j], m[k], cd);
                    break;
                }
            }
        }
        return;
    }
    for( int i = s ; i < 10 ; i++ )
    {
        n[d] = i;
        TestAndDisplay(n, i, d+1);
    }
}