project euler 35

오일러 프로젝트 35 번

소수 중에서 각 자리의 숫자들을 순환시켜도 여전히 소수인 것을 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

순환하는 수를 만드는 건 쉽다. 자리수에 해당하는 10의 제곱수로 나눈 몫과 나머지를 가지고 나머지*10 + 몫으로 순환시킨다. 검사를 빠르게 하기 위해 소수채를 만들고 여기에 있나 없나를 검사한다.

from math import log10, floor

def prime_sieve(bound):

    sieve = [True] * (bound//2)
    for i in range(3, int(bound**.5)+1, 2):
        if sieve[i//2]:
            sieve[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 sieve[i]]

def e35():
    def check(n):
        k = str(n)
        for c in "024568":
            if c in k:
                return False
        c = int(log10(n))
        l = 10**c
        m = n
        for _ in range(c+1):
            q, r = divmod(m, l)
            m = r * 10 + q
            if m not in s:
                return False
        return True

    s = set(prime_sieve(1000000))
    b = [2,5] + list(filter(check, s))
    print(len(b))

%time e35()
# 55
# Wall time: 208 ms