일부 숫자를 치환했을 때 8개의 서로 다른 소수가 생기는 가장 작은 소수

[eng][kor]

느린 풀이

가장 작은 수를 구해야 하므로 알고리즘의 방향은 작은 수에서 큰 수로 진행할 것이다. 또 치환할 자리수를 뽑는 것은 조합이므로, 조합 코드를 만들어야 한다. 그리고 수에 대한 digit을 다뤄야 하므로, 이를 다루는 함수를 많이 만들었던 오일러 49번 문제의 코드를 갖다 쓰자.

이렇게 풀이를 계획하고 첫 코드를 짜서 돌려 보니 96.726 초가 걸린다. 답은 나왔지만, 코드가 꼬인 느낌도 들고 실행시간도 길다. 더 좋은 방법이 없을까?

/*
	 Problem 51 - Prime digit replacements 
 */
#include <iostream>
#include <ctime>
#include <map>
#include <cmath>
#include <vector>
#include <math.h>
#include <string.h>

using namespace std;

std::map<int,int> primes;
bool isprime( int n)
{
	if( n == 2) return true;
	std::map<int,int>::iterator it = primes.find(n);
	if( it != primes.end()) { return true; }

	int s = sqrt( n) + 1;
	for(int i=s; i>1; i--)
	{
		if (n%i ==0) { return false; }
	}

	primes.insert( std::map<int,int>::value_type( n, n));
	return true;
}

int toint( int n[], int size)
{
	int toi = 0;
	for(int i=0; i<size; i++)
	{
		toi += pow(10, i) * n[i];
	}
	return toi;
}

void inc( int n[], int size)
{
	n[0]++;
	for(int i=0; i<size; i++)
	{
		if(n[i] >= 10) {
			if(i+1 < size) {
				n[i+1] += n[i]/10;
			}
			n[i] = n[i]%10;
		} else {
			break;
		}
	}
}

#define MAX 8

int n[MAX] = {0,};

void combination( int arr[], int arrsize, int choose, int nowi, std::vector<int> result, bool* done)
{
	if( choose <= 0) {
		vector<int> replacedNumbers;
		for(int i=0;i<10;i++)
		{
			int r[MAX];
			memcpy( r, n,sizeof(int)*MAX);

			bool nopush = false;
			for( std::vector<int>::iterator it= result.begin(); it!=result.end();++it)
			{
				if( i == 0 && *it == arrsize-1) {
					nopush = true;
					break;
				}
				r[*it] = i;
			}
			if (!nopush){
				replacedNumbers.push_back(toint(r, MAX));
			}
		}

		int nPrimes = 0;
		for(int i=0; i<replacedNumbers.size(); i++)
		{
			if (isprime( replacedNumbers[i])) {
				nPrimes++;
			}
		}

		if( nPrimes == 8) {
			cout << "\tfound!" << endl;
			for(int i=0; i<replacedNumbers.size(); i++)
			{
				if( isprime( replacedNumbers[i])) {
					cout << replacedNumbers[i] << " ";
				}
			}
			cout << endl;

			*done = true;
		}
		return;
	}

	for(int i=nowi; i<arrsize;i++)
	{
		std::vector<int> r(result);
		r.push_back(i);
		combination( arr, arrsize, choose-1, i+1,r, done);
	}
}

int main(int argc, char** argv)
{
	clock_t begin = clock();

	/* starting code */

	n[1] = 1; // starting at 10
	int digits = 1;

	bool done = false;
	while( !done)
	{
		int ntoi = toint( n, MAX);
		int d = int(log10(ntoi)+1);
		if( d> digits) digits = d;

		for(int i=1;i<=digits; i++)
		{
			int digitlist[MAX] = {0,};
			for(int j=0;j<digits-1; j++)
			{
				digitlist[j] = j;
			}
			std::vector<int> c;
			combination( digitlist, digits, i, 0, c, &done); 
		}
		cout << "n=" << ntoi << endl;
		inc( n, MAX);

	}

	/* end of code */
	clock_t end = clock();
	std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
	return 0;
}