소인수분해 구현하기

소인수분해(prime fatorization)는 어떤 합성수를 소인수의 곱으로 표현하는 것을 의미한다. 12는 합성수이며, 1, 2, 3, 4, 6, 12 로 나눠질 수 있다. 이렇게 어떤 합성 수를 인수의 곱으로 표시하는 방법은 다양하지만, 소수들의 곱으로 표현하는 방법은 (순서를 무시하면) 하나의 방법만 존재한다. 12 = 2 * 2 * 3 으로 표시할 수 있다.

소인수 분해를 사용하면 약수의 개수나 모든 약수의 합을 좀 더 쉽게 계산할 수 있다. 물론 이것은 연필과 종이를 사용할 때에 적용될 것 같은 이야기이다. 컴퓨터를 사용하는 소인수 분해의 경우, “소수인 인수를 정하는 것”에 제법 시간이 소요될 수 있기 때문에 실제로 그리 크지 않은 범위의 수에 대해서는 무식하게 루프를 돌면서 나눠보는 것으로 약수를 세거나 더하는 방법이 더 빠를 수 있다.

하지만 이러한 방법은 대상이 되는 수가 매우 크다면 제곱근까지만 루프를 돈다고 해도 여전히 느릴 수 밖에 없다. 이런 경우 소인수분해를 시행하는 것이 더 나은 선택일 수 있다. 소인수분해를 어떤식으로 구현할 수 있는지 살펴보자.

먼저 결과를 어떤 식으로 만들 것인지를 생각해보자. 중복되는 소인수들을 모두 개별 원소로 담고 있는 정수의 리스트로 만들 수도 있을 것이고, (소인수, 지수)의 형태로 두 정수의 튜플로 정리하여, 이러한 튜플의 리스트로 만드는 방법도 있다. 약수의 개수나 약수의 합을 구하는 경우에는 후자의 방식이 더 어울리므로 여기서도 후자의 방식으로 결과를 만들어보겠다.

방법은 다음과 같다.

  1. 입력받은 정수 N을 가장 작은 소수인 2로 나눠본다. 나눌 수 없다면 다음 인수를 찾아야 한다. 나눌 수 있다면 N은 N / 2 가 되고, 2에 대한 지수가 1이 된다. N / 2 에 대해서도 계속 2로 나눌 수 있을 때까지 계속 나누어서 소인수 2의 지수를 얻는다.
  2. 지수가 1이상이라면 (즉 해당 값으로 한 번 이상 나눴다면), (소인수, 지수)의 튜플을 결과에 포함시킨다.
  3. 소인수 p로 N을 더이상 나눌 수 없다면, 그 다음으로 나눌 수 있는 새로운 소인수를 찾는다.
  4. N이 1이 될때까지 위의 연산을 반복한다.

여기서 핵심이 되는 부분은 3에 해당하는 다음 소인수 후보를 찾는 것이다. 제법 성능이 좋은 소수 검사 함수를 가지고 있다 하더라도 p를 증가시켜 가면서 p가 소수인지를 체크하는 방식은 척 보기에도 그다지 효율적이지 않아 보인다. 다른 방법으로는 처음 N이 주어질 때, N 이하의 모든 소수를 구해서, 이들로 나눠보는 것이다. N 이라는 한계값이 있기 때문에 이 과정은 에라토스테네스의 체를 사용해서 처리할 수 있을 것이다. 다른 방법으로는 p보다 크면서 N을 나눌 수 있는 값을 찾아내는 함수를 별도로 작성하는 것이다.

이 글에서는 세 번째 방법을 중심으로 구현해보겠다. 먼저 소인수 분해 함수의 전체적인 얼개는 다음과 같다.

from typing import List, Tuple

def factorization(n: int) -> List[Tuple[int, int]]:
    res = []
    # n 이 2보다 작다면 소인수 분해 불가능
    if n < 2:
        return res
    # 가장 작은 소수인 2 부터 시작한다.
    p = 2
    while n > 1:
        e = 0  # 소인수의 지수
        while n % p == 0:
            n, e = n // p, e + 1
        if e > 0:
            res.append((p, e))
        # p로는 더 이상 나눌 수 없으므로 다음 인수 후보를 찾아야 한다.
        p = < p보다 큰 n을 나눌 수 있는 후보 값 찾기 >
    return res

자, 그렇다면 인수의 후보를 찾는 함수를 작성해보자.

  1. 이 함수는 방금 시행했던 인수 k를 인자로 받는다.
  2. k = 2 이면 다음 후보는 3이다.
  3. k = 3 이면 다음 후보는 5이다.
  4. k = 7 이면 다음 후보는 7이다.
  5. 7 다음은 9가 아닌 11이다. 9는 이미 3의 배수이기 때문이다. 11 다음은 13이며, 다시 13 다음은 17이다. 이것은 k를 3으로 나눈 나머지가 1 이면 2가 아닌 4를 더해야 한다는 의미이다.
  6. 5의 규칙으로 k를 늘려가면서 n으로 나누어지는지 찾아본다. k가 n의제곱근보다 커진다면 n을 나눌 수 있는 값이 더 이상 없다는 뜻으로 남은 n이 소수라는 의미가 된다.

이 함수는 n을 계속 참조하고 있기 때문에 factorization() 함수 내부에 nested 함수로 정의할 수 있다.

def factorization(n):
  ...
  def helper(k: int) -> int:
    if k < 7:
      return (3, 5, 7)[(k - 1) // 2]
    t =  1 if k % 3 == 1 else 0
    l = int(n**0.5 + 0.5) + 1
    while k < l:
      k, t = k + (2, 4)[t], (t + 1) % 2
      if n % k == 0:
        return k
    return n
  ...

소인수 자체가 절대적으로 크지 않다면 n은 발견된 소인수들로 계속해서 나눠나가면서 빠르게 줄어들기 때문에 매우 빠르게 계산된다. 예를 들어 3_800_651, 560_441_670 의 경우에는 1ms 이하로 답이 계산된다.

  • 3,800,651 — (1907, 1), (1993, 1)
  • 560,441,670 — (2, 1), (3, 1), (5, 1), (7, 1), (13, 1), (103, 1), (1993, 1)

하지만 소인수 자체가 매우 크다면 이 역시도 적지 않은 시간이 소요된다. 아래 예는 대략 6초 정도의 시간이 소요된다. 심지어 이 수는 너무 커서 에라토스테네스의 체를 쓸 수도 없는 상황이긴 하다. (칸 하나에 1바이트만 쓴다 해도 10엑사바이트를…)

  • 10,000,128,400,406,539 = (100000567, 1), (100000717, 1)

극단적으로 큰 수의 소인수분해를 컴퓨터로 계산하는데에는 General Number Field Sieve라는 알고리듬이 가장 빠르게 작동할 수 있다고 한다. (100자리 이상) 그렇다고 이 알고리듬이 킹왕짱인 건 아니고 값의 범위에 따라서 가장 효율적인 알고리듬들은 각자 존재한다. 열심히 공부해보면 이런 알고리듬들의 파이썬 구현을 작성할 수 있을지 모르겠으나, 이쯤 되면 성능을 생각한다면 파이썬외의 방법을 강구하는 것이 옳겠다.

소스코드

https://gist.github.com/5677c02ab1f02acfa1598de63eb3ed64