태그 보관물: project euler

project euler 50

오일러 프로젝트 50 번

41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.

    41 = 2 + 3 + 5 + 7 + 11 + 13

이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.

1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.

1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?

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

최적화가 매우 중요한 문제이다. 1분 이내에 푸는 방법을 찾기도 꽤 벅찼다. 계속 읽기

project euler 49

오일러 프로젝트 49 번

1487, 4817, 8147은 3330씩 늘어나는 등차수열입니다. 이 수열에는 특이한 점이 두 가지 있습니다.

세 수는 모두 소수입니다.
세 수는 각각 다른 수의 자릿수를 바꿔서 만들 수 있는 순열(permutation)입니다.
1자리, 2자리, 3자리의 소수 중에서는 위와 같은 성질을 갖는 수열이 존재하지 않습니다. 하지만 4자리라면 위엣것 말고도 또 다른 수열이 존재합니다.

그 수열의 세 항을 이었을 때 만들어지는 12자리 숫자는 무엇입니까?

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

4자리 소수를 모두 구한다음, 순열인것끼리 묶는다. (정렬된 숫자값을 키로 하고, 해당 순열의 소수 리스트를 값으로 하는 사전을 이용한다.)

그 다음 원소가 3개인 항목을 대상으로 세 수가 등차수열인지 판단한다. 이는 정렬된 수 a, b, c 에서 c == 2 * b – a 인지를 확인해보면 된다.

def is_prime(n):
    if n < 2:
        return False
    if n == 2 or n == 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 make_key(n:int) -> int:
    return int("".join(sorted(str(n))))

def find_seq(l):
    for i, v in enumerate(sorted(l)):
        remain = l[i+1:]
        for s in remain:
            dd = s + s - v
            if dd in remain:
                print("".join([str(x) for x in (v, s, s+dd)]))

def e49():     
    samples = [x for x in range(1000, 10000) if is_prime(x)]
    d = {}
    for p in samples:
        k = make_key(p)
        if k not in d:
            d[k] = [p]
        else:
            d[k].append(p)
    b = [x for x in d.values() if len(x) >= 3]
    for x in b:
        find_seq(x)

%time e49()
#2969629915928
#1487481712964
#Wall time: 23 ms