We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.
What is the largest n-digit pandigital prime that exists?
1부터 n까지 한번씩 모든 숫자를 사용하여 만들어진 n자리 숫자를 pandigital이라 부른다. 예를 들어, 2143은 4자리 pandigital이며 또한 소수이다.
가장 큰 n자리 pandigital 소수는 무엇인가?
--------------------------------------------------------------------------
답을 구하는 기본 원리는 간단하다. 각 자리 숫자에 대한 pandigital을 구하고 소수인지 확인하여 가장 큰 값을 찾으면 되는 것이다. 실제 그렇게 구현했고, 시간도 많이 걸리지 않아 다음 문제로 넘어갔던 것 같은데, 이 글을 쓰면서 생각해보니 효율을 높일 방법이 여러가지가 있어 보인다.
우선, 작은 숫자부터 올라가면 모든 조합을 확인해야 가장 큰 pandigital 소수를 찾을 수 있지만, 큰 숫자부터 내려오면서 pandigital을 검증하면 가장 먼저 찾는 소수가 가장 큰 pandigital 소수가 된다. 그리고, 1~9의 합이 3의 배수이기 때문에 9자리는 모든 숫자가 3으로 나눠지므로 소수가 아니고, 1~8의 합도 마찬가지로 3의 배수이기 때문에 8자리 숫자도 검증할 필요가 없다. 즉, 7자리 숫자의 가장 큰 pandigital에서 시작하여 내려오면서 가장 먼저 나오는 소수가 해답이 되므로, 훨씬 빠른 시간에 답을 구할 수 있을 것이다.