오일러 프로젝트 37

소수 3797에는 왼쪽부터 자리수를 하나씩 없애거나 (3797, 797, 97, 7), 오른쪽부터 없애도 (3797, 379, 79, 7) 모두 소수가 되는 성질이 있습니다. 이런 성질을 가진 소수는 단 11개만이 존재합니다. 이것을 모두 찾아서 합을 구하세요. (참고, 한자리 소수인 2, 3, 5, 7 은 제외합니다.)

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

어떤 소수의 왼쪽과 오른쪽에서 자리수를 하나씩 지워나갔을 때, 그 숫자도 계속 소수가 되는 소수를 찾는 문제이다. 이 문제는 순환 소수와 비슷한 구석이 있다. 소수(prime number)의 끝자리(1의 자리)에 올 수 있는 숫자는 무엇일까? 우선 0, 2, 4, 6, 8로 끝나는 수는 짝수이므로 올 수 없다. 5로 끝나는 수도 5의 배수이므로 올 수 없다. 결국 (두자리 이상의) 소수의 1의 자리에는 1, 3, 7, 9 만이 올 수 있다.

왼쪽이나 오른쪽에서 숫자를 하나씩 지워나간다면 결국 숫자를 이루는 모든 수들이 1의 자리에 오게 되므로, 애초에 이 성질을 가진 수들은 모두 1, 3, 7, 9로만 이루어 질 것이며, 한 자리 소수가 되어야 하므로 첫 자리와 끝 자리 숫자는 3 혹은 7만 가능하다. 첫째자리는 그 조건이 조금 더 완화되어 2와 5가 올 수 있다. (실제 풀이에 도움되는 정보는 아니다.)

왼쪽에서 숫자를 하나씩 제거하는 것과 오른쪽에서 숫자를 하나씩 제거하는 것을 따로 생각하면 복잡/귀찮을 수 있지만, 이것을 중간 지점에서 가른 것을 모은 것이라고 이해하면 의외로 간단한 코드로 풀린다. 예를 들어 ‘12345’를 100으로 나눈 몫과 나머지는 각각 (123, 45) 인데, 이는 오른쪽에서 두 숫자를 지운 것과, 왼쪽에서 세 숫자를 지운 것에 해당한다.

아래의 span() 함수는 나눗셈을 통해서 숫자들을 가른 결과를 리스트로 반환한다.

from math import log10

def span(n: int) -> list[int]:
  res = [n]
  l = int(log10(n))
  for i in range(l):
    res.extend(divmod(n, 10**(i + 1)))
  return res

span(123)
# -> [123, 12, 3, 1, 23]

우리가 찾고자 하는 값은 span() 함수를 적용하여 얻는 정수들이 모두 소수인 경우가 되겠다. 따라서 값을 검사하는 test() 함수는 아래와 같이 간단하게 작성할 수 있다.

test = lambda x: all(map(isprime, span(x)))

문제의 조건에서는 양 끝의 숫자가 2, 3, 7 (2는 왼쪽 끝자리에만 올 수 있다)이어야하므로, 테스트를 통과할 수 있는 가장 작은 수는 23이다. 23부터 시작하여 조건을 만족하는 수 11개를 찾으면 된다. 참고로 이 문제의 조건을 만족하는 가장 큰 소수는 739397로 백만 보다 작기 때문에 요즘(2023년) 기준으로 왠만한 컴퓨터 사양에서는 파이썬으로도 충분히 1초 이내에 답을 구할 수 있다.

def main():
  # n : 테스트할 정수
  # k : 찾아야 할 소수
  # s : 누적합
  # i : 4, 6 중에서 어떤 값을 더할 지
  n, k, s, i = 23, 11, 0, 0
  ds = (4, 6)
  while k > 0:
    if test(n):
      k, s  = k - 1, s + n
    n, i = n + ds[i], i ^ 1
  return s

참고로 증가치를 번갈아가면서 적용하기 위해서는 i 값이 0, 1, 0, 1 을 반복해야 하는데 (i + 1) % 2 로 구할수도 있지만, XOR 연산을 사용하면 더 빠르고 간단하게 0, 1을 번갈아 만들 수 있다.