Login
Immutable PageDiscussionInfoAttachments

Please use a more selective search term instead of ""

Clear message
iz/競技プログラミング/Project Euler 021 Amicable numbers

MMA

http://projecteuler.net/problem=21

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

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

   1 #!/usr/bin/env ruby
   2 
   3 @cache = {}
   4 def divisors_sum(n)
   5   return @cache[n] if @cache[n]
   6   return @cache[n] = (1...n).inject do |a, p|
   7     if n % p == 0 
   8       a + p
   9     else
  10       a
  11     end
  12   end
  13 end
  14 
  15 ret = 0
  16 1.upto(10000) do |i|
  17   (i+1).upto(10000) do |j|
  18     if divisors_sum(i) == j && divisors_sum(j) == i
  19       ret += i + j
  20     end
  21   end
  22 end
  23 p ret