프로젝트 오일러 037

이 문제는 35번 원형 소수 문제와 비슷해보이지만 실제로는 상당히 다른 문제입니다. 우선 가장 큰 차이로 찾아야 하는 소수의 개수는 주어졌지만, 그 범위가 주어지지 않았습니다. 따라서 소수체를 사용할 수 없으니 범위를 좁히는 것에 상당한 노력을 기울여야 합니다.

한자리씩 없애 나가기

‘1234’가 있을 때 이를 10, 100, 1000으로 나눈 몫과 나머지를 나열하면 [123, 4, 12, 34, 1, 234]가 됩니다. 여기에 원래 수를 추가하면 [1, 12, 123, 1234, 234, 34, 4]으로 원래 수와 양쪽을 절단한 수의 목록이 됩니다.

이 원리를 이용하여 정수 n을 양쪽으로 절단한 수의 모음을 만들 수 있습니다.

def parts(n: int) -> list[int]:
    l = int(log10(n)) + 1
    res = [divmod(n, 10**i) for i in range(1, l)]
    res = [n] + list(sum(res, ()))
    return [] if any(x > 3 and (x % 2 == 0 or x % 3 == 0) for x in res) else res

여기서 2, 3이 아닌 짝수나 3의 배수가 포함되어 있으면 빈 배열을 리턴하도록 했습니다. 이렇게하면 불필요하게 소수검사를 수행하는 횟수를 줄일 수 있기 때문입니다.

범위를 줄이기

그 외에 한쪽을 절단한 값이 소수가 되지 않는 경우를 생각해봅시다. 조건을 만족하는 수는 그 자체가 소수이므로 짝수이거나 5의 배수가 되지 않아야 하고 1의 자리에는 한 자리 소수가 와야 합니다. 그러니 1의 자리가 0, 1, 2, 4, 5, 6, 8, 9는 올 수 없습니다. 즉 1의 자리에는 3과 7만 올 수 있습니다. 20이하의 수에서는 이 조건을 만족하는 수가 없기에 23이 조건을 만족하는 가장 작은 수입니다. 이로부터 23, 27, 34, 37… 이렇게 +4, +6을 반복하여 더하면서 검사하면 불필요한 대상을 제외할 수 있습니다.

소수 판별 검사 역시 결과를 캐시해두면 도움이 될 겁니다. (실험해보면 의외로 소수 판정 검사의 캐싱은 5%정도의 성능향상을 보입니다.) 가장 성능에 큰 영향을 주는 부분은 3, 7로 끝나는 수만 검사하는 가드입니다.

def main():
    s = set()
    k = 23
    while len(s) < 11:
        for i in (4, 6):
            xs = parts(k)
            if xs and all(isprime(x) for x in xs):
                s.add(k)
            k += i
    print(sum(s), s)
print(main())