http://projecteuler.net/problem=21

10000以下の友愛数の和を求める。

現実的な時間で全探索できる（計算量O(10^8)）。一瞬では終わらない。

{{{#!highlight ruby
#!/usr/bin/env ruby

@cache = {}
def divisors_sum(n)
  return @cache[n] if @cache[n]
  return @cache[n] = (1...n).inject do |a, p|
    if n % p == 0 
      a + p
    else
      a
    end
  end
end

ret = 0
1.upto(10000) do |i|
  (i+1).upto(10000) do |j|
    if divisors_sum(i) == j && divisors_sum(j) == i
      ret += i + j
    end
  end
end
p ret

}}}