소수 중에서 각 자리의 숫자들을 순환시켜도 여전히 소수인 것을 circular prime이라고 합니다. 예를 들어 197은 971, 719가 모두 소수이므로 여기에 해당합니다. 이런 소수는 100 밑으로 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97 처럼 13개가 있습니다. 그러면 1,000,000 밑으로는 모두 몇 개나 있을까요?
http://euler.synap.co.kr/prob_detail.php?id=35
접근
백만 아래에서 순환하는 모든 소수를 찾아야 한다. 기본적인 범위가 백만 단위이고 수행해야 할 연산도 많기 때문에 만만치 않은 문제인 것처럼 보인다. 일단 범위를 줄이는 것 대신에 숫자를 한자리씩 순환시키는 숫자를 만드는 방법을 먼저 살펴보자.
가장 쉽게 생각해 볼 수 있는 것은 숫자를 문자열로 변환한 후, 처리하는 방법을 생각할 수 있다. 이 시리즈에서 여러 번 언급했지만, 문자열과 정수를 상호 변환하는 것은 효율이 좋지 않은 경우가 많다. (파이썬 버전이 높아질수록 이와 관련된 성능은 점점 향상되는 듯 하긴하다.) 따라서 상용로그를 사용해서 정수 그 자체를 처리하는 것이 성능상으로는 더 바람직하다.
정수 n을 입력 받아서, 이 정수의 숫자를 이동시켜서 순환한 값들의 목록을 리턴하는 함수를 아래와 같이 작성할 수 있다.
from math import log10
def shift(n: int) -> list[int]:
l = int(log10(n))
res = []
for i in range(l):
q, r = divmod(n, 10 ** (i + 1))
res.append(r * 10**(l - i) + q)
return res
print(shift(12345))
# [51234, 45123, 34512, 23451]보초 세우기
순환하는 수들이 모두 소수가 된다는 것은, 모든 숫자들이 일의 자리에 온다는 것을 의미하는데, 그렇다면 순환 소수에는 들어갈 수 없는 숫자가 있다는 것이다. 예를 들어 0, 2, 4, 6, 8 중 하나의 숫자가 중간에 포함되어 있다면 순환하는 값들 중에서는 짝수가 되는 수가 있다는 의미이다. 같은 이유로 5도 사용될 수 없다. 즉, {1, 3, 7, 9} 만 사용하여 만든 숫자만 순환소수가 될 수 있다.
이러한 숫자를 체크하는 로직을 추가한다.
def guard(n: int) -> bool:
s = {1, 3, 7, 9}
while n > 0:
n, r = divmod(n, 10)
if r not in s:
return True
return False빠른 소수 검사
이 문제의 조건 중에 가장 매력적인 점은 순환 소수를 찾아야 하는 범위의 상한값이 정해여 있다. 따라서,
- 에라토스테네스의 체를 사용하여 소수의 목록을 구하고
- 소수 목록에 있는 소수에 대해서만 검사하면 된다.
- 백만 이하의 소수를 순환시키면 항상 백만이하의 소수만 나오므로, 소수 검사는 목록에 그 값이 있는지만 확인하면 된다. set을 사용한다면 아주 빠르게 알 수 있다.
이상의 내용을 조합하여 문제를 풀어보자.
def sieve(bound: int) -> list[int]:
s = [True] * (bound // 2)
for i in range(3, int(bound**.5) + 1, 2):
if s[i//2]:
s[i*i//2::i] = [False] * ((bound - i * i - 1) // (2 * i) + 1)
return [2] + [2*i+1 for i in range(1, bound // 2) if s[i]]
%%time
s = sieve(1_000_000)
t, res = set(s), 2
# res에는 2와 5가 포함되어 있다.
for p in s:
if guard(p):
continue
if all(map(lambda x: x in t, shift(p))):
res += 1
print(res)