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

project euler 38

오일러 프로젝트 38 번

숫자 192에 1, 2, 3을 각각 곱합니다.

    192 × 1 = 192
    192 × 2 = 384
    192 × 3 = 576

곱한 결과를 모두 이어보면 192384576 이고, 이것은 1 ~ 9 팬디지털(pandigital)인 숫자입니다. 이런 과정을 편의상 '곱해서 이어붙이기'라고 부르기로 합니다.

같은 식으로 9와 (1, 2, 3, 4, 5)를 곱해서 이어붙이면 918273645 라는 1 ~ 9 팬디지털 숫자를 얻습니다.

어떤 정수와 (1, 2, ... , n)을 곱해서 이어붙였을 때 얻을 수 있는 가장 큰 아홉자리의 1 ~ 9 팬디지털 숫자는 무엇입니까? (단 n > 1)

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

n 을 증가시켜가면서 1, 2, 3 .. 9 와 곱한 결과들을 모아서 팬디지털이 되는지 검사한다. 즉 문제의 내용 그대로를 코딩하면 된다.

def test(n):
    s = ""
    for i in range(1, 10):
        s += str(i * n)
        if len(s) >= 9:
            break
    if "".join(sorted(s)) == "123456789":
        return s
    return None

def e038():
    a = []
    print(max(filter(lambda x:x is not None, (test(x) for x in range(1, 100000)))))

%time e038()
# 932718654
# Wall time: 645 ms

project euler 37

오일러 프로젝트 37 번

소수 3797에는 왼쪽부터 자리수를 하나씩 없애거나 (3797, 797, 97, 7) 오른쪽부터 없애도 (3797, 379, 37, 3) 모두 소수가 되는 성질이 있습니다.

이런 성질을 가진 소수는 단 11개만이 존재합니다. 이것을 모두 찾아서 합을 구하세요.

(참고: 2, 3, 5, 7은 제외합니다)

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

조건에 맞는 소수들을 세면서 11개가 될때까지 검사를 수행해야 한다. 왼쪽에서 한자리씩 없애거나 오른쪽에서 한자리씩 없애는 것은 간단한 편인데 (상용로그를 이용하면 쉽다) 시간이 적지 않게 소모된다. 성능을 최적화하는 방법 몇 가지를 살펴보자.

  1. 숫자를 하나씩 제거해나가면 원래 값보다 계속 작아진다. 따라서 소수 판별함수는 메모이제이션한다.
  2. 문제의 조건에 의해 1의 자리는 3, 7 중 하나의 숫자만 올 수 있다. 이걸 미리 검사하면 수행시간이 절반으로 줄어든다.
  3. 마찬가지로 첫자리에는 2가 올 수 있지만, 그외 나머지 자리에는 짝수 숫자가 올 수 없다. 이 부분이 엄청나게 많은 경우를 제거한다.

2, 3의 제약 조건이 없을 때 약 6~7초 가량 걸리던 것이 저 제약 조건만으로 500ms대로 단축됐다.

from math import log10

def rFront(n):
    a = [n]
    while n > 0:
        l = 10**int(log10(n))
        n = n % l
        a.append(n)
    return a[1:-1]

def rRear(n):
    a = [n]
    while n > 0:
        n = n // 10
        a.append(n)
    return a[1:-1]

def memoize(f):
    cache = {}
    def wrapper(a):
        if a in cache:
            return cache[a]
        r = f(a)
        cache[a] = r
        return r
    return wrapper

@memoize
def is_prime(n):
    if n < 2:
        return False
    if n is 2 or n is 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    if n < 9:
        return True
    k = 5
    l = n ** 0.5
    while k <= l:
        if n % k == 0 or n % (k+2) == 0:
            return False
        k += 6
    return True


def check(n):

    if n % 10 not in (3, 7):
        return False

    s = str(n)[1:]
    for c in "02468":
        if c in s:
            return False

    if is_prime(n):
        for i in rFront(n):
            if not is_prime(i):
                return False
        for i in rRear(n):
            if not is_prime(i):
                return False
    else:
        return False
    return True

def e37():
    res = []
    a = 11
    c = 0
    while len(res) < 11:
        if check(a):
            res.append(a)
        a += [2, 4][c]
        c = (c + 1) % 2
    print(sum(res))

%time e37()
# 748317
# Wall time: 565 ms