프로젝트 오일러 047

문제

47번 문제

서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우는?

사이냅소프트

소인수분해

어떤 정수 N이 몇 개의 소인수를 갖는지 알아보기 위해서는 소인수분해를 해야 합니다. 이 문제에서는 각 소인수가 몇 개씩 곱해지는지는 중요하지 않지만, 그 구분은 실제로는 소인수 분해 함수의 성능에 큰 영향을 주지는 않으니, 소인수분해 함수를 작성하는 것이 필요합니다. 소인수 분해 함수는 다음과 같이 작성할 수 있습니다.

1. 2는 유일한 짝수인 소수입니다. N을 2로 나누어봅니다. 2로 나누어진다면 더 이상 나눌 수 없을 때까지 나누어봅니다. 나눌 때마다 N은 절반의 크기로 줄어듭니다. 나눈 횟수가 1이상이면 (2, 횟수)의 순서쌍을 기록합니다.
2. 남은 N에 대해서는 3, 5, 7, ... 이렇게 홀수로 1.의 방법과 똑같은 방법으로 나누어보고, 나눈 횟수가 1보다 크면 (나눈 값, 횟수)의 순서쌍을 기록합니다.
3. 나누는 수는 3, 5, 7, 9 와 같이 커지겠지만, 3으로 나눌 수 있을만큼 이미 나누었기 때문에 9로는 나눌 수 없을 것입니다. 따라서 N을 나눌 수 있는 수들은 모두 1외에는 약수를 갖지 않는 소수일 것입니다.
4. 나누는 수 커지든, 반대로 N이 줄어들 든, 나누는 수가 N보다 커지면 반복은 끝납니다. 실제로는 나누는 수가 N의 제곱근보다 크다면 더 이상 나누기가 불가능합니다. 그런 경우에는 N이 1보다 크다면 (N, 1)이 소인수분해의 결과에 포함됩니다.

def factorize(n: int) -> dict[int, int]:
    m = n
    res: dict[int, int] = {}
    e = 0
    while n % 2 == 0:
        n, e = n // 2, e + 1
    if e > 0:
        res[2] = e
    k = 3
    while k <= n**0.5:
        e = 0
        while n % k == 0:
            n, e = n // k, e + 1
        if e > 0:
            res[k] = e
        k += 2
    if n > 1:
        res[n] = 1
    return res


def main():
    n = 2 * 3 * 5 * 7
    j = 0
    while j < 4:
        j = (j + 1) if len(factorize(n)) == 4 else 0
        n += 1
    print(n - 4)


if __name__ == "__main__":
    main()

서로 다른 4개의 소인수를 갖는 가장 작은 값은 2 * 3 * 5 * 7 = 210입니다. 210부터 하나씩 올라가면서 소인수분해의 결과가 4개이면 카운트를 올리고, 그렇지 않으면 카운트를 0으로 리셋하는 동작을 반복하여 카운트가 4개 되는 시점에 반복을 멈추면 됩니다.

혹은 all() 함수를 사용하는 방법이 있는데, 이 방법을 사용하면 같은 값에 대해서 4번씩 소인수분해를 반복하게 되므로, 결과를 캐싱했다가 사용하는 메모이제이션 기법을 도입하는 것을 고려해볼 수 있습니다.