오일러 프로젝트 47

오일러 프로젝트 47번은 서로 겹치지 않는 소인수를 갖는 자연수가 연속해서 네 번 나오는 경우를 찾는 것이다. 이 문제는 크게 어렵지 않아 보인다. 간단히 어떤 자연수 N을 소인수분해하여 소인수가 4가지 나오고, N+1을 소인수분해하여 소인수가 4가지 나왔을 때 두 자연수의 소인수 사이에 겹치는 값이 없어야 한다. 이렇게 4개의 연속한 자연수가 “그 직전” 수와 겹치는 소인수가 없이 4개씩 나오는 경우를 찾는다. 소인수분해만 할 수 있으면 푸는 것 자체는 어렵지 않지만, C로 작성된 코드로도 40~50초가 걸렸다는 사람이 부지기수일 정도로 성능 최적화 측면에서 상당한 난이도를 자랑하는 문제이다.

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

접근

처음에 서로 다른 소인수를 가진 연속한 네 자연수를 찾으라고 해서, 모두 다른 16개의 소인수가 나와야 한다고 생각했는데, 문제를 잘 읽어보면 바로 이웃한 두 수만 겹치는 소인수가 없으면 된다. 그럼에도 불구하고 이 문제는 시간과의 싸움이 되며, 현재까지로서는 이 결과가 최선이라 하겠다.

문제의 성공적인 해결을 위해서는 소인수분해과정을 가능한 빠르게 처리할 수 있는 함수를 작성해야 한다. 이를 위해서 다음의 전략을 취한다.

소인수를 구하는 과정에서 나눠보는 수는 2부터 3, 5, 7, 11, 13, 17, … 로 나오게 한다.
나눠지는 수를 찾아서 나누고 나면, 그 다음 수를 찾기 위해서는 방금 사용한 수 보다 더 큰 제수의 후보를 찾도록 한다.

인수의 거듭제곱값은 필요 없고, 인수간의 겹치는 값을 빠르게 찾기 위해서는 소인수의 집합(set)을 리턴하는 함수를 작성한다.

def getFactors(n):
  def divisor_over(a):
    ## 처음 작은 값에 대해서는 고정된 값을 시험해본다.
    ## 이 값들로 n은 나눠지지 않을 수 있다. 
    if a < 3:
      return a + 1
    if a is 3:
      return 5
    k = a
    i, l = 0, n**0.5
    ds = (4, 2) if k % 3 is 1 else (2, 4)
    while k <= l:
      if n % k is 0:
        return k
      k, i = (k + ds[i], (i + 1) % 2)
    return n

  a = 1
  p = set()
  while n > 1:
    a = divisor_over(a)
    while n % a is 0:
      p.add(a)
      n //= a
  return p

소수 검사와 마찬가지로 k = 5부터 시작해서 올라가는 방법도 있지만, 조금이라도 시간을 덜기위해서 코드를 변형했다. a가 1,2,3인 경우가 애매한데, 이 경우는 이상하게 단순하게 안나와서 그냥 쓰기로 했다. 대신에 나눠보기 전에 한 번 더 검사하는 대신에 루프 내에서 세트에 나누는 값을 반복해서 넣는 처리를 하기로 했다. (이 부분이 while: 루프 앞에 검사하는 로직을 세우는 것 보다 더 빠르게 돌아간다.)

소인수분해 로직이 만들어졌으니 최종 코드는 아래와 같이 정리된다.

def e47():
  ## 초기값은 가장 작은 네 소인수를 갖는 값부터 시작한다. 
  s = 2*3*5*7 + 1
  f0 = {2,3,5,7}
  c, m = 0, set() ## m 은 빈 집합인지 검사하기 위해 생성한다. == {} 으로 검사하면 늘 False가 된다.
  while True:
    f1 = getFactors(s) # (2*3*5*7의 다음 숫자부터 검사)
    if len(f1) is 4 and f1.intersection(f0) == m:
      c += 1 
    else:
      c = 0
    ## 조건을 만족하면 카운트를 올리고, 실패하면 카운트를 0으로 초기화한다.
    if c > 3:
      print(s - 3)
      return
    f0 = f1
    s += 1

코드 자체는 복잡하지 않아보인다. 하지만 소인수검사 로직을 조금이라도 더 빠르게 하기 위해서 얼마나 많은 노력이 들어갔는지 모르겠다. 여기서 몇 가지 팁을 발견했다.

set 의 삽입 및 탐색 성능은 매우 우수하다. p.add(a) 를 수십번 더 호출하는 것이 a가 n으로 나눠지는 검사를 한 번 더하는 것보다 더 빠른 성능이 나올 정도이다. 또한 교집합 검사에도 놀라운 성능을 보여준다.
비어있는 집합을 검사하려 할 때 {} 리터럴을 쓰지 말 것. 파이썬에서 빈 중괄호는 빈 사전을 뜻한다. 빈 사전과 빈 집합을 == 으로 비교하는 것은 늘 False가 된다.

위 코드를 실행했을 때 좀 오래된 PC에서도 2.5초 수준에서 답이 나온다. 이것도 cPython에서는 놀라운 결과라 생각한다.

보너스 : Swift 풀이

소인수분해할 때, 다음 제수를 찾는 로직을 약간 손봤고, 무려 0.5초만에 풀렸다. (IBM Swift Sandbox에서는 0.2초 걸렸다) : [Gist보기]

Wireframe