Project Euler : Problem 21 『Amicable numbers』

友愛。 / is_kyoto_jp

問題

projecteuler.net
　n自身を除くnの約数を全て足した数をd(n)と定義する。
この時d(a) = b、d(b) = a、a ≠ bを満たす数a, bを友愛数(Amicable number)と呼ぶ。*1
10000以下の全ての友愛数の和を求めよ。

約数計算するのめんどくさい

　10000まで各数を割り算して約数計算するのめんどくさいので、どうにか手を抜けないかと考えた。
例として10までの約数を書く。

d(1) = 1
d(2) = 1
d(3) = 1
d(4) = 1, 2
d(5) = 1
d(6) = 1, 2, 3
d(7) = 1
d(8) = 1, 2, 4
d(9) = 1, 3
d(10) = 1, 2, 5

　パッと見てすぐ分かるのは、全部が1を約数に持っていること(当然)
次に2に関係する数をピックアップする。

d(2) = 1
d(4) = 1, 2
d(6) = 1, 2, 3
d(8) = 1, 2, 4
d(10) = 1, 2, 5

　d(2)の後、2の倍数の約数d(2n)に2が含まれているのがわかる。
何となく見えてきたので次は3。

d(3) = 1
d(6) = 1, 2, 3
d(9) = 1, 3

　d(3)の後、d(3n)に3が含まれている。
というわけで、d(x)の後d(xn)は約数としてxが含まれることがわかった。
わざわざ割り算しなくて済むよ。

　訳数が出れば、その和はどっかに保存しておけばいいし。

友愛数の定義

　友愛数の定義は
d(a) = b、d(b) = a、a ≠ bを満たす数a, b
なので、
d(x)がxにならない、かつd(d(x))がxになる数
を求めればいい。

コード

using System;
using System.Diagnostics;

namespace Problem21
{
    class Program
    {
        //上限
        static int MaxNum = 10000;
        //約数の和リスト
        static Int64[] SumDivisors;

        static void Main(string[] args)
        {

            Debug.WriteLine(SumOfAmicableNumbers());
        }

        /// <summary>
        /// 問題を解く
        /// </summary>
        static Int64 SumOfAmicableNumbers()
        {
            CreateSumDivisorsArray();

            return SumAmicable();
        }

        /// <summary>
        /// 約数の和リストを作成
        /// </summary>
        static void CreateSumDivisorsArray()
        {
            SumDivisors = new Int64[MaxNum + 1];

            for (int p = 2; p <= SumDivisors.Length / 2; p++)
            {
                for (int i = p * 2; i < SumDivisors.Length; i += p)
                {
                    SumDivisors[i] += p;
                }
            }

            for (int i = 2; i < SumDivisors.Length; i++)
            {
                SumDivisors[i] += 1;

                if (SumDivisors[i] > MaxNum) SumDivisors[i] = 0;
            }
        }

        /// <summary>
        /// 友愛数の総和を求める
        /// </summary>
        static Int64 SumAmicable()
        {
            Int64 sum = 0;

            for (int i = 2; i < SumDivisors.Length; i++)
            {
                if (SumDivisors[i] != i & SumDivisors[SumDivisors[i]] == i)
                {
                    sum += i;
                }
            }

            return sum;
        }
    }
}