C# で Project Euler に挑戦: Problem 3

問題

最大の素因数

13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.

• Problem3 - Project Euler (公式サイト)
• Problem3 - Project Euler (和訳サイト)

ぼくの解答

static void Main(string[] args)
{
    var n = 600851475143;

    // まず約数を求め、その中から素数を見つけることで素因数を獲得します。
    var answer = n.Divisors().Where(i => i.IsPrime()).Max();
    Console.WriteLine(answer);

    Console.ReadLine();
}

public static class NumberHelper
{
    public static IEnumerable<long> Divisors(this long n)
    {
        long minor = 1;
        long greater = n;
        var counter = minor;

        while (counter < greater)
        {
            if (n % counter == 0)
            {
                minor = counter;
                greater = n / minor;

                yield return minor;
                yield return greater;
            }

            counter++;
        }            
    } 

    public static bool IsPrime(this long n)
    {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n%2 == 0) return false;

        for (var i = 3; i*i < n; i += 2)
        {
            if (n%i == 0) return false;
        }

        return true;
    }
}

解説

素因数は約数を求めた後、その中から素数を見つけるのが簡単そうだったので、約数を求めるメソッドと、簡単な素数判定メソッドを拡張メソッドで用意しました。

素因数のリストが手に入れば、あとは最大値を返すだけです。

約数の求め方

約数を求めるときは 1 から順に試しに割っていきますが、もし割り切れたら、割った数(カウンタ)と除算の結果の両方が約数なので、同時に約数として返していきます。

このとき、除算の結果(商)より大きい約数が今後登場することはないので、終了値を商に置き換えて行きます。

例えば 20 の約数を求めるときは、

1. 1 で割ってみる -> 20 / 1 = 20 -> 1 と 20 が約数 -> カウンタの終了値を 20 に
2. 2 で割ってみる -> 20 / 2 = 10 -> 2 と 10 が約数 -> カウンタの終了値を 10 に
3. 3 で割ってみる -> 割り切れないので次
4. 4 で割ってみる -> 20 / 4 = 5 -> 4 と 5 が約数 -> カウンタの終了値を 5 に
5. カウンタが終了値(5)になったので終わり。約数は、1, 20, 2, 10, 4, 5

という感じです。

素数判定

簡単な試し割りです。一度約数を見つけて、その後素数判定をしているので簡単な試し割りで十分かなということで。