소인수 분해했을 때, 서로 다른 소인수가 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을 소인수 분해하는 과정을 생각해보자.
- 120을 2로 나눠보면 나눠지는 것을 알 수 있다. ( 2 * 60 )
- 60 역시 2로 나눠진다. 이렇게 나눈 몫을 계속해서 2로 나눠보자 ( 2 * 2 * 2 * 15)
- 120은 2로 세 번까지 나눌 수 있음을 알 수 있다. 남은 15는 2로 나눠지지 않으므로 4, 6, 8과 같은 짝수로는 더 이상 나눠지지 않을 것이다.
- 남은 15를 3으로 나눠보자. 나눠지고 몫으로 5가 남는다.
- 남은 5를 4로 나눠보자. 4는 소수가 아니지만, 이미 4의 소인수인 2로 나눌만큼 나눴기 때문에 나눠지지 않을 것이다.
- 남은 5를 5로 나눠보자. 나눠진다. 몫이 1이 되었고 이제 소인수 분해가 끝났다.
- 이상의 계산에서 2는 3회, 3은 1회, 5는 1회로 나눴다. 따라서 120을 소인수 분해하면 2^3 * 3^1 * 5^1 이 된다는 것을 알았다.
소인수 분해의 과정을 일반화하면 다음과 같다.
- 소인수 분해하는 대상을 n 이라 한다.
- k = 2 부터 시작하고, k로 나눈 횟수 e = 0으로 시작한다.
- n이 k로 나눠질 수 있다면 n = n / k 가 되고, 이 때 e는 매번 1씩 올려준다.
- k로 n을 나눌 수 없게되면, e > 0 일 때 (k, e)를 결과에 추가한다.
- 다음 k 값을 선택하고, e = 0으로 초기화하여 3~4를 반복한다.
- 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 값을 선택하는” 부분을 별도의 헬퍼함수로 작성할 것이다. 이 함수가 활용할 수 있는 조건을 살펴보자.
- 이 헬퍼함수는 현재 k값을 받아서 그보다 큰 k값의 후보를 리턴한다.
- 소인수 분해 함수 내에서만 사용된다. 따라서 이전에 주어졌던 k값보다 작은 값이 다시 입력으로 주어지지는 않을 것이다.
- k = 1, 2, 3 인 경우에는 순서대로 각각 2, 3, 5 를 리턴한다.
- k 값을 늘려나가는데, k 값은 현재 n 값의 제곱근보다 커질 필요가 없다.
- 소수 검사 함수때와 비슷하게 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