프로젝트 오일러 #60 소수쌍 집합

이번 문제는 처음으로 난이도 20%짜리 문제입니다.

 

 

소수쌍이라고 해서 특별한 수학적인 내용이 들어가 있는 것은 아닙니다.

3, 7 이 두개의 소수가 있다고 하면, 이 두개의 소수를 단순하게 이어서 37, 73을 만들었을 때, 이 수들도 소수가 되면, (3, 7)은 소수쌍이 되는 것입니다.

 

이러한 소수들은 무한히 존재하겠지만, 빈도가 많지는 않습니다.

 

이 문제를 풀기 위해서는 메모리를 사용해서 해당되는 셋들을 만들것인가가 중요했습니다.  그렇게 하려면, 너무 자료구조가 복잡해서, 약간의 꼼수를 사용했습니다.

 

일단, 소수들을 결합하기 위한 재료는 미리 저장을 해놓고, 소수들을 결합한 결과에 대한 소수 검사는 별도의 라이브러리를 이용했습니다.  그리고 min이라는 정적 변수를 두어서, 이 값을 이용해서 현재 구해진 최소값보다 예상값이 크면 더 이상 진행하지 않도록 했습니다.

 

이렇게 해도 시간이 꽤 걸리네요.  다시 좋은 알고리즘으로 짜고 싶기는 했지만, 일단 이 선에서 마무리를 했습니다.

 

아래는 소스입니다.

 

 

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

#define N   5
#define LIMIT   5000

int getminsum(int primes[], int pcount, int pset[][2], int n, int s, int sum)
{
    static int min = 0x7fffffff;

    if( n >= N ) return sum;
    for( int i = s ; i < pcount ; i++ )
    {
        if( sum+primes[i]*(N-n) >= min ) break;
        int c = 10;
        while( primes[i] >= c ) c *= 10;
        bool find = true;
        for( int j = 0 ; j < n ; j++ )
        {
            int t;
            t = pset[j][0]*c+primes[i];
            if( !isPrime(t) ) { find = false; break; }
            t = primes[i]*pset[j][1]+pset[j][0];
            if( !isPrime(t) ) { find = false; break; }
        }
        if( find == false ) continue;
        pset[n][0] = primes[i];
        pset[n][1] = c;
        int t = getminsum(primes, pcount, pset, n+1, i+1, sum+primes[i]);
        if( t < min ) min = t;
    }
    return min;
}

void solve1()
{
    static int primes[LIMIT];
    int pcount = 0;

    primes[pcount++] = 3;
    primes[pcount++] = 5;
    primes[pcount++] = 7;
    for( int p = 11 ; pcount < LIMIT ; p += 2 )
    {
        bool isPrime = true;
        for( int i = 0 ; primes[i]*primes[i] <= p ; i++ )
        {
            if( (p%primes[i]) == 0 ) { isPrime = false; break; }
        }
        if( isPrime ) primes[pcount++] = p;
    }

    int pset[5][2];
    int minsum = getminsum(primes, LIMIT, pset, 0, 0, 0);

    printf("Ans = %d\n", minsum);
}