왼쪽이나 오른쪽에서 한자리씩 없애가도 여전히 소수인 수의 합은?

[eng][kor]

수를 한자리씩 잘라내며 소수인지 확인하는 작업은 지금까지 비슷한 작업을 많이 해왔으므로 그냥 짜면 되지만..

내가 며칠간 고민했던 부분은 알고리즘을 돌릴 ‘상한’ 을 어떻게 정할지였다. 문제에서는 truncatable prime 이 단 11개 존재한다고 했으므로 11개로 제한을 걸면 되지만, 이렇게 딱 찝어 특정 수로 제한을 거는 것이 찝찝했던 것이다.

결국, 고민해보다 일반적인 상한을 거는 방법을 찾지 못하고 그냥 11개까지 수를 찾으면 루프를 종료하는 식으로 풀었다. 아쉬운 마음이 남는 풀이. ^^;;

reddit에 나와 비슷한 고민을 한 쓰레드가 있다. 봐도 잘 모르겠군.. ㅠㅠ

/*
  Problem 37 -Truncatable primes 
*/

#include <iostream>
#include <ctime>
#include <map>
#include <vector>
#include <cmath>
#include <string.h>
#include <stdio.h>

using namespace std;

std::map<int,int> primes;

bool isLeftSidedPrime( char buf[]) 
{
	int buflen = strlen( buf);
	for(int i=0; i<buflen; i++)
	{
		int sided = 0;
		for(int j=0; j<=i; j++)
		{
			sided += (buf[j] - '0') * pow(10, i-j);
		}
//		cout << "l sided=" << sided << endl;
		if( sided == 0 || sided == 1) { return false; }
		if( sided == 2) { continue; } 

  	std::map<int,int>::iterator it = primes.find(sided);
  	if( it != primes.end()) { continue; } 
		else {
			int s = sqrt( sided)+1;
			for(int j=s; j>1; j--)
			{
				if( sided%j == 0) { return false;}
			}
		}
		primes.insert( std::map<int,int>::value_type( sided, sided));
	}
	return true;
}

bool isRightSidedPrime( char buf[]) 
{
	int buflen = strlen( buf);
	for(int i=0; i<buflen; i++)
	{
		int sided = 0;
		for(int j=i; j<buflen; j++)
		{
			sided += (buf[j] - '0') * pow(10, buflen-j-1);
		}
//		cout << "r sided=" << sided << endl;
		if( sided == 0 || sided == 1) { return false; }
		if( sided == 2) { continue; } 

  	std::map<int,int>::iterator it = primes.find(sided);
  	if( it != primes.end()) { continue; } 
		else {
			int s = sqrt( sided)+1;
			for(int j=s; j>1; j--)
			{
				if( sided%j == 0) { return false;}
			}
		}
		primes.insert( std::map<int,int>::value_type( sided, sided));
	}
	return true;
}

std::map<int,int> bothSidedPrimes;

bool isBothSidedPrime( int n)
{
	char buf[1024] = {0,};
	sprintf( buf, "%d", n);
	
	if (!isLeftSidedPrime( buf)) { return false; }
	if (!isRightSidedPrime( buf)) { return false; }
//	cout << "buf=" << buf << ", reverse=" << reverse << endl;

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

void checkTruncatablePrimes( int n)
{
	for(int i=0; i<9; i++)
	{
		int newn = n*10 + i;
		if( isBothSidedPrime( newn)) {
			checkTruncatablePrimes( newn);
		}
	}
	
	for(int i=0; i<99; i++)
	{
		int newn = n*100 + i;
		if( isBothSidedPrime( newn)) {
			checkTruncatablePrimes( newn);
		}
	}
}

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

	for(int i=0;; i++)
	{
		checkTruncatablePrimes(i);
		if (bothSidedPrimes.size() >= 15) { break; }
	}


	int sum = 0;
	cout << "size = " << bothSidedPrimes.size() << endl;;
	for( std::map<int, int>::iterator it = bothSidedPrimes.begin(); it != bothSidedPrimes.end(); ++it)
	{
		cout << it->first << endl;
		sum += it->first;
	}

	sum -= (2+3+5+7);

	cout << "sum=" << sum << endl;

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