프로젝트 오일러 041

문제

41번 문제

<var>n</var>자리 팬디지털 소수 중에서 가장 큰 수

사이냅소프트

팬디지털 수와 소수

n자리 팬디지털 수에는 1부터 n까지의 모든 숫자가 하나씩 포함됩니다. 따라서 특정한 자리 수의 팬디지털 수들은 결코 소수가 되지 않는 것들이 있습니다. 예를 들어 2자리 팬디지털 수인 12와 21은 각 자리 수의 합이 3이므로 3의 배수입니다. 마찬가지로 여기에 3이 추가되는 3자리 팬디지털 수도 모두 소수가 아닙니다. 따라서 1~n까지의 합이 3의 배수가 되지 않는 팬디지털 수는 1-4 팬디지털과 1-7팬디지털밖에 없습니다.

• 1 + 2 = 3 ··· 0
• 1 + 2 + 3 = 6 ··· 0
• 1 + 2 + 3 + 4 = 10 ··· 1
• 1 + 2 + 3 + 4 + 5 = 15 ··· 0
• 1 + 2 + 3 + 4 + 5 + 6 = 21 ··· 0
• 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 ··· 1
• 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36 ··· 0
• 1 + 2 + ... + 8 + 9 = 45 ··· 0
• 1 + 2 + ... + 8 + 9 + 10 = 55 ··· 0

사실 이렇게 범위만 정할 수 있어도 큰 도움이 됩니다. 7,654,321이하의 모든 소수를 구한 다음, 팬디지털 수인지 검사하는 방법도 있겠습니다. 혹은 다른 방법으로는 7654321의 순열을 순서대로 만들어서 소수인지 검사하는 것도 좋은 방법입니다.

저는 후자의 방식을 택하도록 하겠습니다. 7654321부터 순열로 점점 작은 값을 만들면서 소수임을 검사합니다. 소수검사, 순열생성 모두 지금까지 문제를 풀면서 만들어보았던 기능을 그대로 재사용할 수 있습니다.

from functools import reduce


def perms[T](xs: list[T], n=0):
    def helper(head, tail, k):
        if k == 0:
            yield head
            return
        for i, x in enumerate(tail):
            yield from helper((*head, x), (*tail[:i], *tail[i + 1 :]), k - 1)

    yield from helper(tuple(), tuple(xs), n if n > 0 else len(xs))


def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    k, l = 5, int(n**0.5 + 1.5)
    while k < l:
        if n % k == 0 or n % (k + 2) == 0:
            return False
        k += 6
    return True


dump = lambda xs: reduce(lambda x, y: 10 * x + y, xs)


def main(n):
    n = [int(c) for c in sorted(str(n), revoerse=True)]
    for ns in perms(n):
        p = dump(ns)
        if is_prime(p):
            return p


print(main())

1-4 팬디지털 수 중에서 가장 큰 것은 4,321이고 이 수는 놀랍게도(?) 소수입니다. 만약 7자리 팬디지털 수 중에서 답이 나오지 않는다면 4321이 답이겠죠.