프로젝트 오일러 118번

Using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set {2, 5, 47, 89, 631}, all of the elements belonging to it are prime.

How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?

---

1 부터 9까지 모든 자연수들을 한 번씩만 사용하여 자연수들을 만든다면 여러 가지 가능성이 있다. 예를 들어, 집합 {2, 5, 47, 89, 631} 은 이런식으로 만든 자연수들의 집합이다. 그런데 이 집합은 한 가지 특징이 있다. 모든 원소들이 소수로 이루어져 있다는 것이다.

이런 식으로 1부터 9까지의 자연수들을 한 번씩만 사용하여 자연수들의 집합을 만들 때, 모든 원소가 소수들로 구성된 서로 다른 집합은 몇 개를 만들 수 있을까? 

먼저 9개의 숫자를 이용하여 몇 개의 소수를 만들 것인가 결정해야 한다. 이전에 풀었던 31번 문제를 이용하면 다음의 결과를 얻을 수 있다.

(1, 1, 1, 2, 2, 2) (1, 1, 1, 1, 2, 3)

(1, 1, 1, 1, 5) (1, 1, 1, 2, 4) (1, 1, 1, 3, 3) (1, 1, 2, 2, 3) (1, 2, 2, 2, 2)

(1, 1, 1, 6) (1, 1, 2, 5) (1, 1, 3, 4) (1, 2, 2, 4) (1, 2, 3, 3) (2, 2, 2, 3)

(1, 1, 7) (1, 2, 6) (1, 3, 5) (1, 4, 4) (2, 2, 5) (2, 3, 4) (3, 3, 3)

(1, 8) (2, 7) (3, 6) (4, 5)

예를 들어, (1, 1, 1, 2, 2, 2) 는 한 자리 소수 3개와 두 자리 소수 3개를 나타낸다고 생각하면 된다. 당연히 (4, 5)는 네 자리 소수 1개와 다섯 자리 소수 1개를 나타낸다고 생각하면 된다. 

여기서 왜 소수의 최대 개수를 6개로 제한했을까?

1~9 까지의 자연수로 최대한 많은 소수를 만들려면 일단 한 자리 소수를 모두 고려해야 하는데 2, 3, 5, 7 의 4개가 가능하다. 이것들을 제외한 나머지 숫자들인 1, 4, 6, 8, 9 인데 2를 제외한 모든 소수는 홀수이므로 끝자리에 올 수 있는 후보가 1, 9 두 개 밖에 없다. 따라서 최대한 만들 수 있는 소수의 개수를 6개로 제한한 것이다.

또 1~9까지 9개의 수로 이루어진 9자리 숫자들에는 소수가 없다는 것을 금방 확인할 수 있기 때문에 9자리 숫자 하나로 이루어진 집합은 제외하였다. (permutations을 사용하면 쉽게 확인할 수 있다.)

이제 소수들의 집합을 찾아나가는 방법을 살펴보자.

예를 들어, (1, 1, 2, 2, 3)은 한 자리 소수 2개, 두 자리 소수 2개, 세 자리 소수 1개로 이루어진 집합을 의미한다. 제일 먼저 할 일은 {1, 2, 3, 4, 5, 6, 7, 8, 9} 에서 permutation를 이용하여 한 자리 수들을 모두 만들어 내고 그 중에서 소수만을 추려내는 일이다. 이렇게 하면 {2, 3, 5, 7} 을 얻을 수 있게 된다. 이제 {2, 3, 5, 7}로부터 combination을 이용하여 소수 2개를 선택한다. 만약 {2, 3}이 선택되었다면 그 다음 단계는 {1, 4, 5, 6, 7, 8, 9}에서 permutation을 이용하여 두 자리 수들을 모두 만들어 내고 그 중에서 소수만을 추려내는 것이다. 이렇게 하면 {97, 67, 71, 41, 79, 47, 17, 19, 89, 59, 61} 를 얻을 수 있다. 다시 여기에서 combination을 이용하여 2개의 소수를 골라낸다. 이때 {97, 67} 은 불가능하다. 7이 양쪽 수에 모두 포함되어 있기 때문이다. {67, 89}과 같이 같은 숫자가 없도록 두 소수를 골라내야 한다. 이제 남은 {1, 4, 5} 를 이용하여 3자리 소수를 만들어 내야 한다. 여기서 만들 수 있는 소수는 {541} 이므로 우리가 찾는 집합은 {2, 3, 67, 89, 541} 이 되는 것이다. 

위와 같은 과정을 표에 등장하는 모든 경우에 대해서 다 수행해야 한다.

말로는 쉽게 되는데 실제로 코딩을 해 보면 상당히 복잡하다. 끈기를 가지고 도전해 보시길...

다른 분들은 얼마나 빠르게 답이 나오는지 모르겠지만, python 을 이용하여 약 15초 만에 답이 나왔다.