프로젝트 오일러 035

숫자를 원형으로 순환하기

“abc”라고 표시하는 세 자리 자연수가 있다고 할 때, 이 수를 순환시키면 “abc”, “bca”, “cab”가 됩니다.

숫자를 순환시킨 수는 이 수의 자리수만큼 만들 수 있습니다.
0부터 2까지 10의 거듭제곱으로 나눈 몫과 나머지에 대해서, 나머지에 10의 거듭제곱을 곱하여 합하면 순환시킨 수를 만들 수 있습니다.
예를 들어, “123”을 10의 2제곱으로 나누면 “1”, “23”이 됩니다. 나머지 “23”에 10의 1제곱을 곱하고 “1”을 더하면 “231”이 됩니다.

자리수는 상용로그를 취하고 소수점 이하를 버린 값에 1을 더하면 구할 수 있습니다. 이 성질을 사용해서 다음과 같이 특정한 수 n에 대해 자리 수를 순환시킨 값을 set로 생성하는 함수 shift()를 작성해봅시다.

def shift(n: int) -> set[int]:
    "n의 숫자를 순환시킨 수들의 집합"
    # l: 자리 수
    l = int(log10(n)) + 1
    return set((n // 10**i) + (n % 10**i * (10 ** (l - i))) for i in range(l))

혹은 문자열을 사용해도 됩니다. 순환을 고민할 필요 없이, 문자열을 두 번써서, “abcabc”로 만든 다음, 0, 1, 2번째 인덱스에서 3글자씩을 추출하여 정수로 만들면 순환시킨 숫자가 됩니다.

def shift2(n: int) -> set[int]:
    l = int(log10(n)) + 1
    s = f'{n}{n}'
    return set(int(s[i:l+i]) for i in range(l))

풀이

프로젝트 오일러 문제들을 풀면서 우리는 이미 소수 검사 함수를 작성한 바 있고, 이 함수의 성능은 나름대로 쓸만하다는 것도 어느 정도 인정할 수 있습니다. 그런데 이 문제에서는 수의 범위가 제시되어 있습니다. 1백만 이하의 모든 원형 소수를 찾는 것입니다. 만약 1백만 이하의 소수를 모두 가지고 있다면 set의 멤버심 검사 연산을 통해서 아주 빠르게 소수 여부를 알 수 있습니다.

shift() 함수는 정수의 세트(set)를 만드는 함수로 설계했습니다. 파이썬의 set는 |, &, <, >과 같은 연산을 지원합니다.

A | B : A와 B의 합집합을 생성합니다.
A & B : A와 B의 교집합을 생성합니다.
A - B : A와 B의 차집합을 생성합니다.
a in A : a가 A의 원소인지 검사합니다.
A < B : A가 B의 부분집합인지 검사합니다. (즉, A의 모든 원소가 B의 원소인지 검사)

순환하여 만든 정수의 세트가 1백만 이하의 소수 세트에 포함된다면 모든 수가 소수라는 것을 쉽게 확인할 수 있습니다. 따라서 에라토스테네스의 체를 만들고, 각 소수에 대해서 순환

문제에서 아주 중요한 힌트를 하나 주고 있습니다. 바로 1백만 이하의 모든 원형 소수를 찾으라고 했습니다. 결국 100만 이하의 수가 소수일 때, 그 수를 원형으로 순환시킨 모든 수가 소수인지를 검사하면 되는 문제 같습니다. 이미 우리는 꽤 쓸만한 소수 검사 함수도 작성해 보았고, 이 문제에서는 원형으로 순환하는 목록을 만드는 함수도 작성했습니다.

하지만 이 문제의 가장 중요한 힌트는 ‘백만 이하’입니다. 범위가 정해져 있다는 이야기입니다. 정해진 범위 내의 모든 소수를 찾는 가장 빠른 방법은 에라토스테네스의 체입니다. 이 소수들을 하나의 set에 넣어둔다면, 백만 이하의 정수에 대해 멤버십 테스트를 하는 것만으로, 최소한의 시간으로 소수인지 여부를 검사할 수 있습니다.

위에서 순환 그룹을 만들 때 리스트가 아닌 세트를 생성한 것도 그러한 이유입니다. set는 차집합, 교집합, 합집합을 만드는 연산자가 정의되어 있고, <, > 연산자를 사용해서 포함관계를 표현할 수도 있습니다. 특정한 수의 순환 집합이 모두 소수라면, 소수 set의 부분집합인지를 검사하여 모두 소수인지를 쉽게 알아낼 수 있습니다.

한 자리 소수도 순환소수에 포함시키는 것으로 문제에서는 설명하고 있으므로 별도의 예외 처리는 필요 없습니다.

from math import log10
def shift(n: int) -> set[int]:
    "n의 숫자를 순환시킨 수들의 집합"
    l = int(log10(n)) + 1
    s = f"{n}{n}"
    return set(int(s[i : l + i]) for i in range(l))


def seive(n: int) -> list[int]:
    s = [True] * (n + 1)
    s[:2] = [False, False]
    for i in range(2, int(n**0.5) + 1):
        if s[i]:
            s[i * 2 :: i] = [False] * ((n - i) // i)
    return [i for (i, x) in enumerate(s) if x]


def main():
    s = seive(100_0000)
    x = set(s)
    res = 0
    for p in s:
        ps = shift(p)
        if ps < x:
            res += 1
    print(res)


if __name__ == "__main__":
    main()