project euler

프로젝트 오일러 012

500개 이상의 약수를 갖는 가장 작은 삼각수.

sooop

sooop

— 5 min read
프로젝트 오일러 012
Photo by Andrej Lišakov / Unsplash

문제

12번 문제
500개 이상의 약수를 갖는 가장 작은 삼각수는?
사이냅소프트

삼각수

삼각수는 '파스칼의 삼각형'에 나오는 수인데, 1부터 n까지의 자연수의 합을 n번째 삼각수라고 합니다. 이는 등비수열의 합으로서, 사실 잘 알려져있는 공식이 있습니다.

$$ T_n = \frac{n ( n + 1)}{2} $$

문제에서는 약수의 개수가 500개를 넘어가는 첫 번째 삼각수를 찾으라고 합니다. 따라서 앞에서 순서대로 삼각수를 만들어나가면서, 약수의 개수가 500개가 되는지를 검사하면 됩니다.

그렇다면 굳이 곱셈이나 나눗셈을 할 필요가 없이, 1 + 2 에다가 3, 4, 5...를 점점 더해나가면 삼각수의 수열을 만들 수 있습니다. (1부터 n까지의 합이니까요)

따라서 만약 '약수의 개수'를 세는 함수가 이미 있다면 전체적인 구조는 다음과 같이 진행할 수 있습니다.

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

약수의 개수

임의의 정수 N의 약수의 개수를 구하는 가장 간단한 방법은 1부터 N의 제곱근에 이루는 수를 모두 나눠서 확인하는 것입니다. 모두 나눠봐야 하는 부담은 있지만 범위는 제곱근까지의 범위니까 확실히 작은 것은 맞습니다.

참고로 1은 나눠보지 않아도 되니까, 약수의 개수는 2부터 시작하고요, 완전제곱수일 때은 약수의 개수가 홀수인 부분을 구현에서 놓치지 않아야 합니다.

def number_of_factors(n: int) -> int:
  s = 2
  k, l = 2, int(n ** 0.5)
  while k <= l:
    if n % k == 0:
      s += 2
    k += 1
  if l * l == n:
    s -= 1
  return s

그런데 생각을 좀 해보죠. 하나의 값으로 나눠질 때 약수의 개수가 2개 증가합니다. 그러면 정답인 N은 그 제곱근까지 나눠봤을 때 250개의 숫자로 나눌 수 있어야 하니 제곱근이 250보다는 클 것입니다. (아니, 1부터 250까지의 모든 자연수의 최소공배수를 생각하면... 250의 제곱 정도는 귀여운 수준이 아닐까요?)

사실 여기까지 했으면 풀이는 가능합니다. 컴퓨터의 사양이나 파이썬 버전에 따라 다르겠지만, 여기까지의 풀이보다는 좀 더 최적화가 되어야 할 것 같습니다.

답이 매우 큰 숫자이기 때문에, 약수의 개수를 좀 더 빠르게 셀 수 있어야 합니다. 소인수분해를 하면 각 지수에 1을 더한 값들을 곱하면 약수의 개수가 됩니다. 즉, 소인수분해를 하는 함수를 구현을 해야 합니다. (그리고, 매우 큰 숫자의 소인수분해를 해야 합니다.)

소인수분해

소인수분해는 어느 정도 크기 이하의 정수에 대해서는 그리 어렵지 않습니다. 대신 분해해야하는 수가 크면 클수록 나눗셈을 많이 해야 합니다. 아래 코드에 있는 소인수분해 로직은 제법 단순하고 나이브해보이기는 합니다만, 그래도 그나마 준수한 성능을 보여줍니다.

from functools import reduce


def factorize(n: int) -> dict[int, int]:
    res: dict[int, int] = {}
    e = 0
    while n % 2 == 0:
        n, e = n // 2, e + 1
    if e > 0:
        res[2] = e
    k, l = 3, int(n**0.5 + 1.5)
    while k < l:
        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 number_of_factors(n: int) -> int:
    if n == 1:
        return 1
    return reduce(lambda x, y: x * y, (x + 1 for x in factorize(n).values()))


def main():
    a, b = 1, 2
    while number_of_factors(a) < 500:
        a, b = a + b, b + 1
    return a

if __name__ == '__main__':
    print(main())
    # print(factorize(120))

소인수분해에서 소수만 나눠보는게 아무래도 나누기 시도를 줄일 수 있는 좋은 방법일 것 같다는 생각이 들지 않나요? N의 제곱근 범위까지의 소수를 에라토스테네스의 체로 빨리 구해서 소인수분해를 하는 것은 어떨까요?

💡
미리 스포하자면, 위의 코드보다 빠르기가 어렵습니다. 실제로 필요한 소인수의 범위는 매우 작기 때문에, 에라토스테네스의 체를 만드는데 쓸모없는 리소스를 낭비하게 됩니다.

파이썬의 루프는 매우 비효율적이라 이런 부분은 좀 한계가 느껴집니다. 줄리아의 경우에는 이러한 단순한 루프에서 JIT의 진가가 발휘됩니다. (10배 이상 빠름)

function nf(n)
  s = 2
  k = 2
  l = Int(floor(sqrt(n) + 1.5))
  while k < l
    n % k == 0 (s += 2)
    k += 1
  end
  return (l * l == n ? s : s - 1)

@time begin
  t, a = 1, 2
  while nf(t) < 500
    t = a * (a + 1) ÷ 2
    a += 1
  end
  println(t)
end

Read more