오일러 프로젝트 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 서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우를 찾으세요. 그 첫번째 숫자는 얼마입니까?
접근
처음에 서로 다른 소인수를 가진 연속한 네 자연수를 찾으라고 해서, 모두 다른 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보기]
// | |
// main.swift | |
// Euler-47 | |
// | |
// Created by sooop on 2017. 8. 25.. | |
// Copyright © 2017년 sooop. All rights reserved. | |
// | |
import Foundation | |
func factors(_ m:Int) -> Set<Int> { | |
var a = 1 | |
var p = Set<Int>() | |
var n = m | |
func divisor(over a: Int) -> Int { | |
switch a { | |
case (1…2): | |
if n % (a + 1) == 0 { return a + 1} | |
return divisor(over: a + 1) | |
case 3: | |
if n % 5 == 0 { return 5 } | |
return divisor(over: 5) | |
default: | |
var k = a | |
var i = 0 | |
let ds = (k % 3 == 1) ? [4, 2] : [2, 4] | |
let l = Int(sqrt(Double(n)) + 0.5) | |
while k <= l { | |
if n % k == 0 { return k } | |
k += ds[i] | |
i = (i + 1) % 2 | |
} | |
return n | |
} | |
} | |
while n > 1 { | |
a = divisor(over: a) | |
p.insert(a) | |
while n % a == 0 { | |
n /= a | |
} | |
} | |
return p | |
} | |
func solve(){ | |
var s = 2*3*5*7 + 1 | |
var f0: Set<Int> = [2,3,5,7] | |
var c = 0 | |
while true { | |
let f1 = factors(s) | |
if f1.count == 4 && f1.intersection(f0).isEmpty { | |
c += 1 | |
if c > 3 { | |
print(s – 3) | |
return | |
} | |
} else { | |
c = 0 | |
} | |
f0 = f1 | |
s += 1 | |
} | |
} | |
func timeit(_ f: () -> ()) { | |
let s = Date() | |
f() | |
print(s.timeIntervalSinceNow * -1000) | |
} | |
timeit(solve) |