오일러 프로젝트 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()