오일러 프로젝트 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