n자리 팬디지털 소수 중에서 가장 큰 수

[eng][kor]

팬디지털 넘버들의 목록을 구한다는 것은 곧 1~9까지의 숫자들로 순열을 만드는 과정이다. 오일러 32번 에서 팬디지털 넘버를 만들기 위한 순열 코드를 만들었고, 오일러 35번 에서 소수를 판별하는 코드를 만들었으므로 갖다 쓰기로 했다.


느린 풀이 

/*
 	Problem 41 - Pandigital prime
*/
	
#include <iostream>
#include <ctime>
#include <vector>
#include <cmath>

using namespace std;

int largest = 0; // solution

bool isprime( int n)
{
  if( n == 2) return true;

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

  return true;
}

void permutation( std::vector<int>nums, std::vector<int> now)
{
	if (nums.size() == 0) {

		int pandigitalNum = 0;
		for(int i=0;i<now.size();i++)
		{
			pandigitalNum += now[i] * pow(10, i);
		}
		if (isprime( pandigitalNum)) {
			cout << "pandigital prime : " << pandigitalNum << endl;
			if ( largest < pandigitalNum) {
				largest = pandigitalNum;
			}
		}
		return;
	}
	
	for(int i=0; i<nums.size(); i++)
	{
		std::vector<int> newone( now);
		std::vector<int> newnums( nums);
		int val = newnums[i];
		newone.push_back( val); 
		newnums.erase( newnums.begin() + i);
		permutation( newnums, newone);
	}
}

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

	/* starting code */
	for(int i=1; i<=9; i++) 
	{
		std::vector<int> nums;
		for(int j=1; j<=i; j++)
		{
			nums.push_back( j);
		}
		std::vector<int> now;
		permutation( nums, now);
	}

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

답은 구했지만 21.1168 초가 걸린다. 더 빠른 방법이 없을까?


아주 약간 개선한 풀이

위의 코드는 가장 작은 자릿수의 팬디지털 넘버부터 소수 여부를 따져보고 있다. 문제에서는 가장 큰 수를 구해야 하므로, 루프를 큰 수부터 거꾸로 돌고 max 를 찾으면 바로 그만 돌도록 바꿔 보았다.

헌데 이것만으로는 단축되지 않았다. 끽해야 0.02초 차이..

순열 함수에서 vector 를 남용한 건가 싶어, 내가 직접 짠 순열 함수 대신 대신 std::next_permutation 을 사용해도, 실행시간은 20.5초.. 많이 줄지 않았다.

#include <algorithm>

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

	/* starting code */
	for(int i=9; i>=1; i--) 
	{
		int nums[9] = {0,};
		for(int j=0; j<i; j++)
		{
			nums[j] = i-j;
		}

		std::sort( nums, nums+i);
		do {
			int pandigital = 0;
			for(int j=0; j<i; j++)
			{
				pandigital += nums[j] * pow(10, j);	
				//cout << nums[j];
			}
			cout << "pan = " << pandigital << endl;
			if( isprime( pandigital)) {
				if( largest < pandigital) {
					largest = pandigital;
				}
			}
			//cout << endl;
		} while( std::next_permutation( nums, nums+i));

		if (largest != 0) {
			break;
		}
	}

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


효율적으로 제외하기

구글링을 해보니 검사할 팬디지털 자리수를 아주 센스있게 대폭 줄일 수 있다.

어떤 팬디지털 수의 각 자릿수를 모두 더한 값은, 같은 자릿수 크기를 가지고 있는 다른 팬디지털 수의 경우에도 모두 같다. 그리고 각 자릿수의 합이 3 의 배수라면, 그 수는 3의 배수이다. 이를 이용해 특정 자리수의 팬디지털 수 검사를 통째로 넘어갈 수 있다.

위 코드에 간단히 sumcheck 변수를 넣어 체크해 주었다.

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

	/* starting code */
	for(int i=9; i>=1; i--) 
	{
		int nums[9] = {0,};

		int sumcheck = 0;
		for(int j=0; j<i; j++)
		{
			nums[j] = i-j;
			sumcheck += nums[j];
		}

		if (sumcheck%3 == 0) continue;

		std::sort( nums, nums+i);
		do {
			int pandigital = 0;
			for(int j=0; j<i; j++)
			{
				pandigital += nums[j] * pow(10, j);	
				//cout << nums[j];
			}
			cout << "pan = " << pandigital << endl;
			if( isprime( pandigital)) {
				if( largest < pandigital) {
					largest = pandigital;
				}
			}
			//cout << endl;
		} while( std::next_permutation( nums, nums+i));

		if (largest != 0) {
			break;
		}
	}

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

여기서 9자리 팬디지털 수와 8자리 팬디지털 수가 계산에서 제외되었고, 실행시간은 0.045초로 매우 빨라졌다. 9자리/8자리 팬디지털 수의 경우의 수가 너무 많아, 이를 계산하는 데 대부분의 시간을 쓰고 있었구나..