[C/C++] 프로젝트 오일러 #49 : 소수 순열

프로젝트 오일러 #49 소수 순열 문제는 좀 복잡해보이기는 하지만, 실제 풀이과정은 단순한 문제입니다. 난이도도 5%로 "매우 쉬움"으로 분류되어 있습니다.

 

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

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

 

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

 

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

 

 

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

 

prime permutations

 

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

//------------------------------------------------
//    Project Euler #49 - Prime Permutations
//        - by Aubrey Choi
//        - created at 2015-03-30
//------------------------------------------------
#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);
    }
}

 

1. 순열을 미리 정의하는 부분

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

4자리 숫자로 만들 수 있는 모든 순열(4!)을 미리 정의해둡니다. 이렇게 하면 순열을 직접 생성하지 않고 배열을 이용해서 빠르게 접근할 수 있습니다.

 

2. 순열을 숫자로 변환하고 소수인지 검사하는 부분

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

• 미리 정의된 순열(perm)을 이용하여 현재 선택된 4개의 숫자(n[])로 만든 숫자를 생성합니다.
• 이미 만들어진 숫자인지 확인한 후(for (int j = 0; j < count; j++) 부분), 중복이 아니고 소수(isPrime(q))이면 배열 m[]에 저장합니다.
• 4자리 숫자만 유효하므로, 1000보다 큰 숫자만 검사합니다.

 

3. 등차수열을 이루는 소수 조합 찾기

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

• 3개 이상의 소수(count >= 3)가 존재할 경우, 이 숫자들 중 등차수열을 이루는 조합을 찾습니다.
• 두 숫자의 차이를 cd로 설정한 후, 세 번째 숫자가 m[j] + cd인지 확인하여 출력합니다.

 

4. 재귀적으로 숫자를 선택하는 부분

for( int i = s ; i < 10 ; i++ )
{
    n[d] = i;
    TestAndDisplay(n, i, d+1);
}

• 0부터 9까지의 숫자를 선택하여 n[] 배열을 채우고, 재귀적으로 4자리 숫자를 구성합니다.
• 숫자의 중복을 허용하면서, 조합을 만들고 순열을 생성하여 소수를 검사합니다.