Original

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

和訳

d(n)をnの真の約数の和と定義する。（真の約数とはn以外の約数のことである。）
もし、d(a) = b かつ d(b) = a （a ≠ b）を満たすとき、aとbは友愛数（親和数）であるという。

例えば、220の約数は1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110なのでd(220) = 284である。
また、284の約数は1, 2, 4, 71, 142なのでd(284) = 220である。

それでは10000未満の友愛数の合計を求めよ

当てにならないソースコード(C#)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using System;
using System.Collections.Generic;

namespace ProjectEuler {
    class Problem21 {
        Dictionary<int,int> sumOfDivisors = new Dictionary<int,int>();
        public Problem21() {
            Console.WriteLine(this.ToString());
            int sum = 0;
            for (int i = 2; i < 10001; i++) {
                if (d(d(i)) == i && d(i) != i) {
                    sum += i;
                }
            }
            Console.WriteLine("> " + sum);
        }

        int d(int n) {
            if (!sumOfDivisors.ContainsKey(n)) {
                int sum = 0;
                for (int j = 1; j <= n / 2; j++) {
                    if (n % j == 0) {
                        sum += j;
                    }
                }
                sumOfDivisors[n] = sum;
            }
            return sumOfDivisors[n];
        }
    }
}


一度求めた約数の和を記録しておくことで無駄な再計算を減らしています。
まだ無駄な部分はありますが・・・。