|
⇤ ← 2012-12-21 10:10:38時点のリビジョン1
サイズ: 554
コメント:
|
← 2012-12-21 10:18:40時点のリビジョン2 ⇥
サイズ: 584
コメント:
|
| 削除された箇所はこのように表示されます。 | 追加された箇所はこのように表示されます。 |
| 行 8: | 行 8: |
| #!/usr/bin/env ruby |
|
| 行 11: | 行 13: |
| ret = 0 1.upto(n-1) do |i| if n % i == 0 ret += i |
return @cache[n] = (1...n).inject do |a, p| if n % p == 0 a + p else a |
| 行 17: | 行 20: |
| return @cache[n] = ret | |
| 行 29: | 行 31: |
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
