오일러 프로젝트 37

오일러 프로젝트 37 번 문제는 순환소수와 약간 비슷하지만, 의외로 성가신 구석이 매우 많은 문제이다. 동시에 잘 설계된 가드가 얼마나 수행 속도를 빠르게 만들어줄 수 있는지에 대한 좋은 예이기도 하다.

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

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

접근

조건에 맞는 소수들을 세면서 11개가 될때까지 검사를 수행해야 한다. 왼쪽에서 한자리씩 없애거나 오른쪽에서 한자리씩 없애는 것은 간단한 편인데 (상용로그를 이용하면 쉽다) 시간이 적지 않게 소모된다. 특히나 이 문제는 수의 범위가 제한되어 있지 않으며 (따라서 소수체를 활용하기 어렵다) 소수를 찾고 그 다음 소수를 찾는 식으로 범위를 확장해나간다. 그리고 그런 와중에 숫자를 제거하면서 검사한다.

성능을 최적화하는 방법 몇 가지를 살펴보자.

  1. 숫자를 하나씩 제거해나가면 원래 값보다 계속 작아진다. 따라서 소수 판별함수는 메모이제이션한다.
  2. 문제의 조건에 의해 1의 자리(끝자리)는 3, 7 중 하나의 숫자만 올 수 있다.[^1]
  3. 마찬가지로 첫자리에는 2가 올 수 있지만, 그외 나머지 자리에는 짝수 숫자 및 5가 올 수 없다.

숫자를 하나씩 지워나간 결과만 리스트로 만드는 방법을 구현하면 나머지는 그리 어렵지 않다. (이 부분이 좀 성가시다.)

문제의 조건으로부터 필요한 코드 조각을 만들어 나가보자

숫자를 뒤에서부터 없애기

숫자를 뒤에서부터 없애는 것은 간단하다. 어떤 자연수 N의 1의 자리가 없어진 수는 10으로 나눈 몫이다. 이를 N이 0이될 때까지 반복할 수 있다.

n = 1345
result = []
while n > 0:
  result.append[n % 10]
  n //= 10

리스트에 숫자를 추가하기 보다는 정해진 길이의 리스트를 만들고 각 요소에 집어넣는 방식을 취해서 다시 구현했다. 이렇게 구현한 이유는 앞에서 숫자를 없애는 것을 연산자만 바꿔서 그대로 이용할 수 있기 때문이다.  (실제로 이 방식으로 구현했을 때 좀 더 빨랐다). log10() 함수를 이용해서 자리수를 구할 수 있고, 10, 100, 100 … 등으로 원하는 자리수까지 끊어가면서 리스트에 넣는다.

from math import log10
def remove_from_back(n):
  c = int(log10(n))  # c = 자리수 - 1
  result = [0] * c
  for i in range(0, c):
    result[i] = n % 10**(i+1)
  return result

remove_from_back(1345)
# [134, 13, 1]

숫자를 앞에서부터 없애기

숫자를 앞에서부터 없애는 것은 나머지 연산이 아니라 몫을 구하는 것으로 교체하면 끝이다.

def remove_from_front(n):
  c = int(log10(n))
  result = [0] * c
  for i in range(0, c):
    result[i] = n // 10**(i+1)
  return result

remove_from_front(1345)
# [5, 45, 345]

체크 함수 만들기

맨 앞자리를 제외한 자리에 0, 2, 4, 5, 6, 8 이 들어간 숫자는 제외한다. 또한 끝자리는 3, 7이어야 하는데, 이는 숫자를 체크하는 과정에서 일정한 폭으로 건너뛰는 것으로 체크되는 대상의 끝자리 숫자가 3, 7인 것을 강제하는 것으로 대체하기로 한다.

def check(n):
  s = str(n)[1:]
  for c in '024568':
    if c in s:
      return False
  if not isPrime(n):
    return False
  for p in (remove_from_front(n) + remove_from_back(n)):
    if not isPrime(p):
      return False
  return True

정리

최종적으로 문제를 풀어보자. 한자리 소수는 모두 제외했고, 두 자리 수 13부터 시작한다. (물론 이 값은 답에 포함되지 않는다.) 끝자리수가 3, 7이 되도록 점프한다.

def p037():
  result = []
  n, i = 13, 0
  while len(result) < 11:
    if check(n):
      result.append(n)
    n = n + (4, 6)[i]
    i = (i + 1) % 2
  print(sum(result))

%time p037
# Wall time: 329ms

보너스 : Swift 풀이

보너스로 Swift 풀이를 첨부한다. Swift4 기준으로 작성되었다.

import Foundation  // log10() 함수는 C의 math.h에 정의되었고, C 표준 함수는 Foundation에 모두 포함되어 있다.

func removeNumberFromFront(_ n: Int) -> [Int] {
  let c = Int(log10(Double(n)))
  return (0..<c).map{ n % Int(pow(10, Double($0 + 1))) }
}

func removeNumberFromBack(_ n: Int) -> [Int] {
  let c = Int(log10(Double(n)))
  return (0..<c).map{ n / Int(pow(10, Double($0 + 1))) }
}

func memoize<T:Hashable, U> (_ f: @escaping: (T) -> U) -> (T) -> U {
  var cache: [T:U] = [:]
  let inner: (T) -> U = { (x) -> U in
    if let result = cache[x] { return result }
    let r = f(x)
    cache[x] = r
    return r
  }
  return inner
}

func __isPrime(_ n: Int) -> Bool {
  if n < 2 { return false }
  if n == 2 || n == 3 { return true }
  if n % 2 == 0 || n % 3 == 0 { return false }
  if n < 10 { return true }
  let l = Int(sqrt(Double(n)) + 0.5)
  var k = 5
  while k <= l {
    if n % k == 0 || n % (k + 2) == 0 { return false }
    k += 6
  }
  return true
} 

let isPrime = memoize(__isPrime)

func check(_ n: Int) -> Bool {
  let s = String(n)
  let t = s[s.index(after: startIndex)...]
  for c in "024568" where t.contains(c) { return false }
  guard isPrime(n) else { return false }
  for p in (removeNumberFromBack(n) + removeNumberFromFront(n)) {
    if !isPrime(p) { return false }
  }
  return true
}

func main() {
  var result: [Int] = []
  var (n, i) = (13, 0)
  while result.count < 11 {
    if check(n) { result.append(n) }
    n = n + [4, 6][i]
    i = (i + 1) % 2
  }
  return result.reduce(0, +)
}