태그 보관물: 오일러프로젝트

project euler 36

오일러 프로젝트 36 번

대칭수(palindrome)인 585는 2진수로 나타내도 10010010012가 되어 여전히 대칭수입니다.

10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합을 구하세요.

(주의: 첫번째 자리가 0이면 대칭수가 아님)


http://euler.synap.co.kr/prob_detail.php?id=36

이진수 변환하는 법은 중학교때 배우니 따로 설명하지 않는다. 또한 짝수의 경우 이진수의 끝자리가 0이므로 굳이 판별할 필요가 없다.

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

def test(n):
    return is_palindrome(n) and bin(n)[2:] == bin(n)[2:][::-1]

def e36():
    r = sum((x for x in range(1, 1000000, 2) if test(x)))
    print(r)

%time e36()

#872187
# Wall time: 549 ms

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