Project Euler 23

Problem 23

Wikipedia で、完全数、不足数、過剰数について調べる。

• 完全数(perfect number)
  • その数自身を除く約数の和が、その数自身と等しい自然数のこと。
  • 例えば 6 (= 1 + 2 + 3)、28 (= 1 + 2 + 4 + 7 + 14) や496が完全数。
• 不足数(deficient number)
  • 自然数のうち、その正の約数の総和が元の数の2倍より小さい数のこと。
  • 例えば15の約数の総和は 1+3+5+15=24<15×2 であるので15は不足数。
• 過剰数(abundant number)
  • 自然数で、その正の約数の総和が元の数の2倍より大きい数のこと。
  • 例えば20の約数の総和は 1+2+4+5+10+20=42>20×2 であるので20は過剰数。

using System;
using System.Collections.Generic;
using System.Linq;

class PE023 {
    static bool isAbundant(int n) {
        int d = 0;
        for (int i = 1; i*2 <= n; i++) {
            if (n % i == 0) {
                d += i;
            }
        }
        return d > n;
    }

    static void Main() {
        int n = 28123;
        var abundants = Enumerable.Range(1, n)
                        .Where(i => isAbundant(i))
                        .ToList();
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            bool found = false;
            foreach (int ab in abundants) {
                int x = i - ab;
                if (ab > x) break;

                if (0 <= abundants.BinarySearch(x)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                ans += i;
            }
        }
        Console.WriteLine(ans);
    }
}