오일러 프로젝트 41

1부터 n까지의 숫자를 하나씩만 써서 만든 n자리 숫자를 팬디지털(pandigital)이라고 부릅니다. 2143은 4자리 팬디지털인데, 이 수는 동시에 소수이기도 합니다. n자리 팬디지털 소수 중에서 가장 큰 수는 무엇입니까?

http://euler.synap.co.kr/prob_detail.php?id=41

접근

단순하게 생각하고 덤비면 곤란한 문제다. 가장 큰 1-9 팬디지털 숫자는 987,654,321로 거꾸로 내려오면서 소수를 찾으면 너무 오래 걸린다.

먼저 팬디지털 숫자의 특성에 대해 생각해보자. 1-9팬디지털 숫자는 모든 자리의 숫자의 합이 45이다. 즉 모든 1-9 팬디지털 수는 9의 배수이기 때문에 소수가 될 수 없다. 같은 이유로 1-8 팬디지털 수도 모두 9의 배수이다. 팬디지털 수의 길이에 따라 각 자리 수의 합을 조사해보면 3의 배수가 아닌 팬디지털 수는 1-7팬디지털 수와 1-4 팬디지털 수 밖에 없다.

# 9 -> 45
# 8 -> 36
# 7 -> 28
# 6 -> 21
# 5 -> 15
# 4 -> 10
# 3 -> 6
# 2 -> 3

따라서 1-7 팬디지털 숫자에 대해서 소수검사를 하면 된다. 참고로 팬디지털 숫자에 대해서만 소수 검사를 하면 되니, 7,654,321부터 1씩 내려오지 않고 1~7 숫자의 순열을 사용해서 검사하면 된다. 순열을 정수로 변환하기 위해서는 앞자리부터 10배하고 다음 자리를 곱하는 과정을 반복하면 된다. 이후 정수로 변환한 값이 소수이면 루프를 중단한다.

만약 1-7 팬디지털 소수가 존재하지 않는다면 1-4 팬디지털 소수를 찾아야 한다. for 루프를 중간에 break 하지 않고 끝까지 도는 경우, else: 절이 있으면 실행되기 때문에, 이 문법을 활용할 수 있다. (스포일러 : 1-7 팬디지털 소수는 존재하기 때문에, 사실 필요하지는 않다.)

from functools import reduce
from itertools import permutations

%%time
for ns in permutations(range(7, 0, -1)):
  n = reduce(lambda x, y: x * 10 + y, ns)
  if isprime(n):
    print(n)
    break
# 1-7 팬디지털 소수를 찾지 못한 경우에 실행되는 코드
# 실제로는 1-7팬디지털 소수가 존재하기 때문에 필요하지는 않다. 
else:
  for ns in permutations(range(4, 0, -1)):
    n = reduce(lambda x, y: x * 10 + y, ns)
    if isprime(n):
      print(n)
      break

소수 검사 함수는, 다른 문제에서도 소개한 바 있는 것 같지만, 다시 한 번 소개한다.

def isprime(n: int) -> bool:
  if n < 2:
    return False
  if n < 4:
    return True
  if n % 2 == 0 or n % 3 == 0:
    return False
  if n < 9:
    return True
  k, l = 5, int(n ** .5 + 1.5)
  while k < l:
    if n % k == 0 or n % (k + 2) == 0:
      return False
    k += 6
  return True