태그 보관물: project euler

project euler 48

오일러 프로젝트 48 번

1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317 입니다.

1^1 + 2^2 + 3^3 + ... + 1000^1000 의 마지막 10자리 숫자는 무엇입니까?

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

C나 Java의 경우 숫자값 타입은 크기의 한계가 정해져있기 때문에 이 문제는 크기의 한계가 없는 큰 수를 위한 데이터타입을 따로 만들어서 풀어야 한다.

파이썬의 int 형은 이미 큰 수를 지원하므로…

def e48():
    print(str(sum((x**x for x in range(1, 1001))))[-10:])

%time e48()
#9110846700
#Wall time: 60 ms

project euler 47

오일러 프로젝트 47 번

서로 다른 두 개의 소인수를 갖는 수들이 처음으로 두 번 연달아 나오는 경우는 다음과 같습니다.

14 = 2 × 7
15 = 3 × 5

서로 다른 세 개의 소인수를 갖는 수들이 처음으로 세 번 연속되는 경우는 다음과 같습니다.

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우를 찾으세요. 그 첫번째 숫자는 얼마입니까?

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

소인수분해하여 이전 수들과 교차하는 소인수가 있는지 체크한다. 이게 은근히 시간이 오래 걸리는데, set을 이용하면 교차부분을 빠르게 찾을 수 있다.

def getFactors(n):
    r = set()
    a = n 
    while a > 1:
        d = divide_helper(a)
        r.add(d)
        while a % d == 0:
            a = a // d
    return r

def divide_helper(n):
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    k = 5
    l = n ** 0.5
    while k <= l:
        if n % k == 0:
            return k
        if n % (k+2) == 0:
            return k+2
        k += 6
    return n

def e47():
    s = 2 * 3 * 5 * 7
    f0 = set()
    c = 0
    while True:
        f1 = getFactors(s)
        if len(f1) == 4 and f1.intersection(f0) == set():
            c += 1
        else:
            c = 0
        if c == 4:
            print(s-3)
            break
        f0 = f1
        s += 1

%time e47()

# 134043
# Wall time: 2.33 s