콘텐츠로 건너뛰기
Home » 오일러 프로젝트 47

오일러 프로젝트 47

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

  • 14 = 2 × 7
  • 15 = 3 × 5

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

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

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

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

접근

서로 다른 소인수 몇 개로 이루어졌는지를 알기 위해서는 주어진 정수를 소인수분해 하여야 한다. (int) -> dict[int, int] 형식의 소인수 분해 함수 factorize()를 작성할 수 있다면, 이 문제는 다음과 같이 풀 수 있다. all() 함수를 사용하여 연속된 네 개의 수가 네 개의 소인수를 가지고 있는지 확인하면 된다.

%%time
a = 2
while True:
  if all(len(factorize(a + i)) == 4 for i in range(4)):
    print(a)
    break
  a += 1

그렇다면 문제의 성공적인 해결은 소인수분해를 얼마나 빠르게 처리할 수 있는가, 즉 얼마나 좋은 factorize() 함수를 작성할 수 있느냐에 달려 있다고 볼 수 있다. ‘좋은’ 소인수분해 함수는 사실 상 없다보 보는 것이 좋다. 괜찮은 방법이라고 알려진 몇 가지 방법들도 각각 장단점이 존재한다. 어느 정도 큰 범위에서 좋은 성능을 내는 방법들이 작은 수의 범위에서는 오히려 복잡해서 성능이 떨어지는 경우도 있다.

어쨌든 우리는 이전에 소인수분해 함수를 작성해본 적이 있고, 이 함수도 제법 쓸만하므로 이걸로 도전해보자.

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

참고로 편의상 all()을 사용하면 코드는 간단해지지만 불필요한 계산을 반복할 수 있기 때문에 factorize() 함수에 메모이제이션을 적용해주는 것도 좋다. 혹은 다음과 같이 반복계산하지 않도록 코드를 작성해줄 수 있다.

# all() 함수를 사용하기
k = 2 * 3 * 5 * 7
while True:
  if all(len(factorize(k + i)) == 4 for i in range(4))
    break
  k += 1
print(k)


# all 함수 없이
a, b = 2 * 3 * 5 * 7, 0
while b < 4:
  b = (b + 1) if len(factorize(a)) == 4 else 0
  a += 1
print(a - 3)

좀 더 빠른 소인수분해

앞에서 사용한 소인수분해 함수는 작은 수에서는 어느 정도 기대한 성능을 보여주지만, n의 값이 크고 소인수가 작은 경우에는 결국 루프를 많이 돌게 되어 성능이 느려진다. 이를 극복하기 위해서는 방금 사용한 소인수 후보 k보다 큰 다른 소인수 후보를 찾아주는 함수를 만들고 활용하는 것이다.

아래와 같이 helper() 함수를 이용한다. 이 함수는 주어진 k보다 크면서 n을 나눌 수 있는 다른 k를 찾아낸다. k = 1, 2, 3, 5,…와 같이 입력하게 될 것이므로 거의 대부분 소수이면서 n을 나눌 수 있는 값을 찾을 수 있다. 코드가 겉으로 보기에는 좀 너저분해보이지만 이 함수를 사용하면 위의 함수보다는 약 40% 가량 더 빠르게 작동한다.

def factorize(n):
  def helper(k):
    '''k보다 크고 n을 나눠볼 수 있는 다음 후보를 리턴함'''
    if k < 3:
      return k + 1
    if k == 3:
      return 5
    l = int(n ** 0.5 + 1.5)
    # 3으로 나눈 나머지가 1인 경우, +2 하면 3의 배수가 되므로...
    j = k if k % 3 == 2 else k + 4
    while j < l:
      if n % j == 0:
        return j
      if n % (j + 2) == 0:
        return j + 2
      j += 6
    return n

  res = {}
  k = 1
  while n > 1:
    e, k = 0, helper(k)
    while n % k == 0:
      n, e =  n // k, e + 1
    if e > 0:
      res[k] = e
    
  return res

소인수 분해를 하기 위해서 n의 제곱근 이하의 소수를 구해서 판정하는 방법도 있을 것인데, 이는 결국 매번 factorize() 함수를 호출할 때마다 소수체를 만들게 되기 때문에 큰 범위에서는 오히려 더 비효율적이다. 대신에 정답이 특정한 값 이하에서 나올 것이라는 것을 보장할 수 있다면, 그 최대값의 제곱근 이하의 소수체가 있다면 훨씬 빠를 수 있다.