Home » 오일러 프로젝트 37

오일러 프로젝트 37

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

Update: 코드를 처음부터 새로 작성했다. 처음 이 풀이를 작성했을 때 처리 시간은 약 8초 가량이었는데, 1초대로 줄였다. 소수 검사 함수를 메모이제이션하는 등의 테크닉을 적용하면 수행 속도를 조금 더 올릴 수 있다.

소수 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개라고 했다. 따라서 시험해야할 대상을 작은 값부터 시작해서 큰 수로 키워나가면서 검사하자. 먼저 자리수를 없앤 숫자들을 어떻게 만들지 생각해보자.

가장 쉽게 떠올릴 수 있는 것은 문자열로 변환하는 것이다. 예를 들어 s = "12345" 라고 하면 앞에서부터 다음과 같이 잘라낼 수 있다.

s[1:] # "2345"
s[2:] # "345"
s[3:] # "45
s[4:] # "5"

이렇게 한 다음에 다시 정수로 변환한다면 다음과 같은 식으로 처리해볼 수 있다.

n = 12345
s = str(n)
l = len(s)
[int(s[i:]) for i in range(1, l)]
# -> [2345, 345, 45, 5]

다른 방법으로는 로그를 사용하는 것이다. 5자리 숫자의 사용로그값은 4.* 이므로, 다음과 같이 쓸 수도 있다.

n = 12345
[ n % 10**(i+1) for i in range(int(log10(n)))]

둘의 성능 차이는 예상했던 것보다는 큰 편은 아니다.

오른쪽을 자르는 경우는 나눗셈을 이용하면 [n // 10**(i+1) for i in range(int(log10(n)))] 이 된다. 이를 사용해서 양쪽을 각각 잘라낸 값을 하나의 리스트로 만드는 함수를 작성할 수 있다.

def slices(n):
  l = int(log10(n))
  left = [n % 10**(i+1) for i in range(l)]
  right = [n // 10**(i+1) for i in range(l)]
  return [*left, n, *right]

이렇게 생성한 배열에서 모든 원소가 소수인지는 all() 함수와 map() 함수를 사용해서 판정해주면 된다.

def test(n):
  return all(map(isprice, slices(n)))

11개의 값을 찾는데 출발점은 13부터 하기로 한다. 끝자리가 3, 7인 값만 검사하면 되기 때문에 +4, +6을 번갈아 하면서 검사한다. 이 때 c 값은 (4, 6)에서 고르는 값으로 0~1을 번갈아 움직이는 데 이 때 i = (i + 1) % 2 하는 것보다 XOR 연산을 사용하는 것이 좀 더 간단하다! (i = i ^ 1)

def main():
  a, b, c = 13, 11, 0
  ds = (4, 6)
  s = 0
  while b > 0:
    if test(a):
      s += a
      b -= 1
    a, c = a + ds[c], c ^ 1
  print(s)

소수 검사 함수를 포함하여 전체 코드는 다음과 같다.

from math import log10
def slices(n):
    l = int(log10(n))
    left = [n % 10**(i+1) for i in range(l)]
    right = [n // 10**(i+1) for i in range(l)]
    return [*left, n, *right]
def test(n):
    return all(map(isprime, slices(n)))
def isprime(n):
    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**0.5+0.5)
    while k <= l:
        if n % k == 0 or n % (k + 2) == 0:
            return False
        k += 6
    return True
def main():
    # n: 검사할 값
    # k: 남은 값의 개수
    # s: 합계
    # i: 간격계산을 위한 인덱스
    n, k, s, i = 13, 11, 0, 0
    ds = (4, 6)
    while k > 0:
        if test(n):
            k, s = k - 1, s + n
        n += ds[i]
        i ^= 1
    print(s)
if __name__ == '__main__':
    main()

댓글 남기기