오일러 프로젝트 12번 (Julia)

500개 이상의 약수를 갖는 삼각수

삼각수는 1부터 n까지의 합으로 구성되는 수이다. 1부터 n까지의 합은 간단한 공식 (n * (n + 1) / 2)으로 구할 수 있으므로 각 삼각수를 구하고, 그 삼각수의 약수의 개수가 500개 이상인지를 판단하면 된다.

어떤 정수 n이 p로 나눠진다면 그 몫인 q 역시 n의 약수가 된다. 따라서 n은 그 제곱근범위 이내에서 나눠보고 약수가 있다면 2씩 더해보면 된다.

function numdivs(n)
  l = Int(floor(sqrt(n) + 0.5))
  # n이 완전제곱수이면 약수의 개수는 홀수가 된다.
  s = l^2 == n ? 1 : 2
  i = 2
  while i < l
    n % i == 0 && (s += 2)
    i += 1
  end
  return s
end

let n = 1, k = 0
  while true
    k = div(n * (n + 1) , 2)
    numdivs(k) >= 500 && (println(k); break)
    n += 1
  end
end