CoffeeScriptでProject Euler #12

CoffeeScript

Problem 12

Problem 12 - PukiWikiを参照

Solution

解いた手順は次の通り。

  1. 三角数を素因数分解する(factorize)。
  2. 同じ素因数を数え上げる(count)。
  3. 約数の個数は同じ素因数の個数がわかっていれば公式的に求まる。約数 - Wikipedia参照。
count = (xs) ->
  output = {}
  (output[x] = if output[x] then output[x] + 1 else 1) for x in xs
  output

factorize = (n) ->
  if n <= 1
    return []
  res = []
  while n % 2 == 0
    res.push(2)
    n /= 2
  limit = Math.sqrt(n+1)
  i = 3
  while i <= limit
    if n % i == 0
      res.push(i)
      n /= i
      limit = Math.sqrt(n+1)
    else
      i += 2
  if n != 1
    res.push(n)
  return res

triangle_sums = (n*(n+1)/2 for n in [1..20000])
for t in triangle_sums
  xs = factorize t
  xs = count(xs)
  num_of_divisor = 1
  (num_of_divisor *= (xs[key] + 1)) for key of xs
  if num_of_divisor > 500
    console.log num_of_divisor
    console.log t
    break

順路：CoffeeScriptでProject Euler #13
逆路：CoffeeScriptでProject Euler #11