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

오일러 프로젝트 12

1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다.  예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다. 이런 식으로 삼각수를 구해 나가면 다음과 같습니다.
 

 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

이 삼각수들의 약수를 구해봅시다.
 

 1: 1
 3: 1, 3
 6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28

위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다. 그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까

http://euler.synap.co.kr/prob_detail.php?id=12

가장 작은 삼각수부터 약수의 개수를 계산하여, 처음으로 약수의 개수가 500을 넘는 값을 찾으면 된다.

삼각수

삼각수는 파스칼의 삼각형에 나오는 수이고, N번째 삼각수는 1부터 N까지의 합으로 계산된다.

\large A_{n} = \frac{n \times (n + 1)}{2}

i = 0, 1, 2, 3, 4, … 일 때 i를 위 공식에 대입해서 구해도 되지만, 1씩 증가하는 값을 누적으로 구해서 사용해도 된다. 만약 어떤 자연수의 약수의 개수를 세는 numbers_of_factors() 라는 함수를 우리가 갖고 있다면, 이 문제는 아래와 같은 코드로 풀어낼 수 있다.

%%time

a, b = 1, 2
while True:
  if number_of_factors(a) > 500:
    break
  a, b = a + b, b + 1
print(a)

약수의 개수 세기

어떤 자연수 N이 자연수 p로 나눠진다면, 두 개의 약수가 있다는 것을 의미한다. 따라서 1부터 N의 거듭제곱까지의 범위에서 각각의 자연수로 나누고, 나눌 수 있다면 약수가 2개씩 있다고 생각하면 된다. 단, N이 완전제곱수인 경우에는 제곱근인 약수는 두 개로 세면 안된다. 이 부분만 주의해서 약수의 개수를 세는 함수를 아래와 같이 작성할 수 있다.

def numbers_of_factors(n):
  l = int(n**0.5)
  s = 1 if l * l == n else 2
  a = 2
  while a <= l:
    if n % a == 0:
      s += 2
    a += 1
  return s

최적화

전체 코드는 앞에서 언급했으니, 실행하면 답을 구할 수 있다. 단, 실제 정답은 꽤 큰 수이기 때문에 삼각수를 순서대로 만드는 방법을 사용하지 않고 1씩 증가시키면서 삼각수인지 검사하려 든다면, 왠만한 전기세로는 답을 볼 수가 없을 것이다. 또한 실제로 이 방법을 사용해도 시간은 꽤 오래 걸리는 편이다.

실제로 적당히 빠른 시간 (3초 이내?) 내에 답을 구하기 위해서는 어느 정도 최적화를 해줘야 하는 문제가 거의 처음으로 나왔다고 볼 수 있겠다. 약수의 개수를 세는 연산이, 비록 제곱근까지만 검사해서 전체 루프 수를 줄이기는 하지만, N값이 크면 클수록 분명 더 많은 루프를 돌면서 나눗셈을 해봐야 하는 것이다. 그래서 시간을 더 단축하고 싶다면, 약수의 개수를 더 빠르게 구하는 방법을 사용해야 한다.

소인수 분해하기

소인수분해는 2부터 1씩 증가하면서 n을 나눌 수 있을만큼 나누고, 나눈 수와 나눈 횟수를 기록해둔다. 이걸 한계값 (제곱근인데, N을 나눠서 더 작은 N’ 가 되었다면 N’의 제곱근까지만 검사하면 된다)까지 반복하고 나눌 수 있는 인수와 그 개수를 리턴해주면 된다.

N이 아주 크다면 이 마저도 ‘나눌 수 있는 다음 후보’를 똑똑하게 찾도록 튜닝을 해야하는데, 일단 최근에는 PC 성능도 좋아졌고, 파이썬 자체의 성능도 좋아졌기 때문에 이 문제에서는 이 정도 함수면 그래도 1초 이내에서 답을 구할 수 있다.

소인수분해를 하면 각각의 소인수와 그 지수들을 얻게 된다. 각 약수는 각각의 소인수를 인수로 포함하거나 하지 않을 수 있기 때문에, 이러한 경우를 모두 세어보면 각 인수의 지수에 + 1씩을 더한 후 모두 곱하면 된다. 따라서 소인수분해 함수를 사용하여 약수의 개수를 구하는 함수는 아래와 같이 작성할 수 있다.

from functools import reduce

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

def numbers_of_factor(n):
  if n == 1:
    return 1
  return reduce(lambda x, y: x * y, (x + 1 for x in factorize(n).values()))

%%time
a, b = 1, 2
while numbers_of_div(a) < 500:
  a, b = a + b, b + 1
print(a)

# 76576500
# CPU times: totla: 750 ms