Home » 오일러 프로젝트 47

오일러 프로젝트 47

소인수 분해했을 때, 서로 다른 소인수가 4개 나오는 수가 연속해서 네 번 나오는 경우를 찾으면 된다. 서로 다른 소인수를 찾는 문제는 결국 소인수 분해를 해야한다는 의미이다. 제법 괜찮은 성능의 소인수분해 함수를 작성하는 것이 핵심이 된다.

서로 다른 두 개의 소인수를 갖는 수들이 처음으로 두 번 연달아 나오는 경우는 다음과 같습니다. 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

접근

문제의 성공적인 해결을 위해서는 소인수분해과정을 가능한 빠르게 처리할 수 있는 함수를 작성해야 한다. ‘좋은’ 소인수 분해 함수란 사실 상 없다고 볼 수 있으며, 괜찮은 방법이라고 알려진 몇 가지 방법들도 각각 장단점이 존재한다. 큰 수의 범위에서 비교적 좋은 성능을 내는 소인수분해 방법이 작은 수의 범위에서는 오히려 성능이 떨어지는 경우도 있다.

소인수는 소수인 인수로, 소수이면서 대상 값을 나눌 수 있는 수를 말한다. 하지만 정작 그 인수가 소수인지 검사할 필요는 없다. 왜냐하면 어떤 수의 모든 소인수들은 항상 서로 소이기 때문이다. 120을 소인수 분해하는 과정을 생각해보자.

  1. 120을 2로 나눠보면 나눠지는 것을 알 수 있다. ( 2 * 60 )
  2. 60 역시 2로 나눠진다. 이렇게 나눈 몫을 계속해서 2로 나눠보자 ( 2 * 2 * 2 * 15)
  3. 120은 2로 세 번까지 나눌 수 있음을 알 수 있다. 남은 15는 2로 나눠지지 않으므로 4, 6, 8과 같은 짝수로는 더 이상 나눠지지 않을 것이다.
  4. 남은 15를 3으로 나눠보자. 나눠지고 몫으로 5가 남는다.
  5. 남은 5를 4로 나눠보자. 4는 소수가 아니지만, 이미 4의 소인수인 2로 나눌만큼 나눴기 때문에 나눠지지 않을 것이다.
  6. 남은 5를 5로 나눠보자. 나눠진다. 몫이 1이 되었고 이제 소인수 분해가 끝났다.
  7. 이상의 계산에서 2는 3회, 3은 1회, 5는 1회로 나눴다. 따라서 120을 소인수 분해하면 2^3 * 3^1 * 5^1 이 된다는 것을 알았다.

소인수 분해의 과정을 일반화하면 다음과 같다.

  1. 소인수 분해하는 대상을 n 이라 한다.
  2. k = 2 부터 시작하고, k로 나눈 횟수 e = 0으로 시작한다.
  3. n이 k로 나눠질 수 있다면 n = n / k 가 되고, 이 때 e는 매번 1씩 올려준다.
  4. k로 n을 나눌 수 없게되면, e > 0 일 때 (k, e)를 결과에 추가한다.
  5. 다음 k 값을 선택하고, e = 0으로 초기화하여 3~4를 반복한다.
  6. n이 1이되면 종료한다.

소인수 분해 함수 작성

위 알고리듬을 그대로 구현하자. 우선 다음 k값을 선택하는 방법을 k를 1씩 증가시킨다고 하면 다음과 같은 식으로 코드를 짤 수 있다.

def factorize(n: int) -> list[tuple[int,int]]:
  res: list[tuple[int,int]] = []
  k = 1
  while n > 1:
    k += 1
    e = 0
    while n % k == 0:
      e, n = e + 1, n // k
    if e > 0:
      res.append((k, e))
  return res

위 함수를 이용해서 4,045,860을 소인수분해하면 [(2, 2), (3, 2), (5, 1), (7, 1), (13, 2), (19, 1)]이라는 결과를 쉽게 얻을 수 있다. 하지만 여기에는 문제가 좀 있다. k 값을 1씩 올려가면서 전량 검사를 하고 있기 때문이다. 4,045,860의 경우에는 값 자체는 크지만, 각각의 소인수가 작기 때문에 결과가 매우 빠르게 나왔다. 하지만 4,041,581은 거의 1초 가까운 시간이 걸린다. 소수이기 때문에 2에서 4백만까지 모든 후보로 다 나눠봐야 하는 것이다.

실제로 소인수분해 함수만 있으면 본 문제를 푸는 코드는 간단하기 때문에 테스트 해 볼 수 있다.

def e047():
  i, j = 2, 0
  while j < 4:
    j = j + 1 if len(factorize(i)) == 4 else 0
    i += 1
  print(i - 4)

실행해보니 거의 5~6분 가량 시간이 걸리는 것 같다. 이건 풀었지만 푼 것이 아니다. 그래서 소인수분해 함수를 개선해야 한다. 소인수 분해 함수의 알고리듬 중에서 “다음 k 값을 선택하는” 방법을 개선하자.

다음 소인수를 빠르게 찾기

여기서는 “다음 k 값을 선택하는” 부분을 별도의 헬퍼함수로 작성할 것이다. 이 함수가 활용할 수 있는 조건을 살펴보자.

  1. 이 헬퍼함수는 현재 k값을 받아서 그보다 큰 k값의 후보를 리턴한다.
  2. 소인수 분해 함수 내에서만 사용된다. 따라서 이전에 주어졌던 k값보다 작은 값이 다시 입력으로 주어지지는 않을 것이다.
  3. k = 1, 2, 3 인 경우에는 순서대로 각각 2, 3, 5 를 리턴한다.
  4. k 값을 늘려나가는데, k 값은 현재 n 값의 제곱근보다 커질 필요가 없다.
  5. 소수 검사 함수때와 비슷하게 k는 3의 배수를 피해서 3a + 1, 3a + 2 인 값만 체크할 것이다.

이상의 로직을 사용해서 다음과 같은 헬퍼함수를 factorize() 함수 내에 추가하자.

def factorize(n: int) -> list[tuple[int,int]]:
  def helper(k: int) -> int:
    if k < 3: return k + 1
    if k == 3: return 5
    l = int(n**0.5+1.5)
    m = k if k % 3 == 2 else k + 4
    # m은 항상 3a + 2 의 형태에서 부터 출발한다. 그래서 m, m + 2로 나누면서 진행한다.
    while m < l:
      if n % m == 0: return m
      if n % (m + 2) == 0: return m + 2
      m += 6
    # 제곱근 이하에서 나눌 수 있는 값을 찾을 수 없다면 현재 n은 소수이다.
    return n
  res: list[tuple[int,int]] = []
  k = 1
  while n > 1:
    # 다음번 k는 helper를 사용해서 얻는다.
    k = helper(k)
    e = 0
    ....

이 헬퍼 함수를 적용한 효과는 놀랍다. 4,041,581을 소인수 분해한 결과는 1ms도 걸리지 않는다. (여기서 일단 기존 함수보다 1000배이상 빠르다는 것을 짐작할 수 있다.) 실제로 개선한 함수를 사용해서 문제를 풀어보면 1초 언저리에서 답이 나오는 것을 확인할 수 있다.

보너스 – 조금 더 빠르게

이 풀이에서 작성한 소인수분해 함수는 각 소인수와 소인수의 지수를 함께 계산해내는 역할을 한다. 지수가 필요없다면 중복되지 않는 소인수의 집합을 구하면 된다. 헬퍼 함수는 동일하게 하되, 지수를 무시하고 set 에 소인수를 중복 추가하는 방식으로 소인수의 집합만 순수하게 구하면, 시간은 좀 더 단축될 수 있다.

def factors(n: int) -> set[int]:
    def helper(k):
        ...
    res = set()
    k, e = 1, 0
    while n > 1:
        e = 0
        k = helper(k)
        while n % k == 0:
            n = n // k
            res.add(k)
    return res

댓글 남기기