Project Euler : Problem 50 『Consecutive prime sum』

問題

projecteuler.net
日本語訳→http://www.odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2050

長い素数列から調べていく

　最初に素数を100万まで求めておく。
その後、2から順番に素数を足していって100万を越える手前で止める。

例えば、こんな感じだったとする

2, 3, 5, 7, …… , P_n-5, P_n-4, P_n-3, P_n-2, P_n-1, P_n

　2からP_n-3まで足すと100万を超えてしまう場合、
2からP_n-4をひとつのまとまりと考える

[2, 3, 5, 7, …… , P_n-5, P_n-4], P_n-3, P_n-2, P_n-1, P_n

　このまとまりが素数かどうかを判別し、素数でない場合はまとまりを1つずらして素数判定をする。

2, [3, 5, 7, …… , P_n-5, P_n-4, P_n-3], P_n-2, P_n-1, P_n

　素数でなければまたずらし＆判定

2, 3, [5, 7, …… , P_n-5, P_n-4, P_n-3, P_n-2], P_n-1, P_n

　ずらし＆判定……とくりかえす

2, 3, 5, [7, …… , P_n-5, P_n-4, P_n-3, P_n-2, P_n-1], P_n

　このように、ひとつずらし＆素数判定を繰り返していくと、どこかでまとまりの値が100万を超えてしまう。
そうなった場合、まとまりの位置を最初に戻して長さを1つ減らす(最大の素数、この場合はP_n-4を削る)。

[2, 3, 5, 7, …… , P_n-5], P_n-4, P_n-3, P_n-2, P_n-1, P_n

　そして再び、ずらし＆判定をおこなっていく。
まとまりが素数だと判定されれば、それは100万以下で総和が素数になる最も長い素数列となる。

うーん

　何かコード書いてる途中からねろねろになってきて変な事してるかもしれない。
見苦しいなと思うけどねろっててしんどいからもうこれでいいや。

コード

using System;
using System.Linq;

namespace Problem50
{
    class Program
    {
        static readonly int Max = 1000000;
        static int[] Primes;
        static int SumPrimes = 0;
        static int LengthPrimes = 0;
        static int Answer = 0;

        static void Main()
        {
            Primes = ES(2, Max);

            SumConsecutivePrimes();

            SearchSoMCP();

            Console.WriteLine(Answer);
        }

        /// <summary>
        /// 問題の、総和が素数になる最も長い素数列を探す
        /// </summary>
        /// <returns>最も大きい素数</returns>
        static void SearchSoMCP()
        {
            int sumBk = SumPrimes;
            int lengthBk = LengthPrimes;

            while (true)
            {
                //素数列を長さそのまま大きい方へずらしながら調べる
                for (int i = 0; i < Primes.Length - LengthPrimes; i++)
                {
                    if (Primes.Contains(SumPrimes) == true)
                    {
                        Answer = SumPrimes;
                        return;
                    }

                    Move(i, LengthPrimes);

                    //素数列の和が100万より大きくなれば終了
                    if (SumPrimes > Max) break;
                }

                //素数列、列の大きさを1つ小さくする(最も大きい素数を削る)
                SumPrimes = sumBk - Primes[lengthBk];
                LengthPrimes--;
                sumBk = SumPrimes;
                lengthBk = LengthPrimes;

                //連続する素数の長さが21未満になれば未発見とする
                if (LengthPrimes < 21) return;
            }
        }

        /// <summary>
        /// 総和が100を超えない最大の素数列の総和を求める
        /// </summary>
        static void SumConsecutivePrimes()
        {
            for (int i = 0; i < Primes.Length; i++)
            {
                SumPrimes += Primes[i];

                //100万超えたら1つ戻す
                if (SumPrimes > Max)
                {
                    SumPrimes -= Primes[i];
                    LengthPrimes = i - 1;
                    break;
                }
            }
        }

        /// <summary>
        /// 大きい方へずらす
        /// </summary>
        /// <param name="i">素数列の尻尾のインデックス</param>
        /// <param name="l">素数列の長さ</param>
        static void Move(int i, int l)
        {
            SumPrimes = SumPrimes - Primes[i] + Primes[i + l + 1];
        }

        //エラトステネスの篩
        static int[] ES(int min, int max)
        {
            int[] ps = new int[max + 1];

            for (int i = 0; i < ps.Length; i++)
            {
                ps[i] = i;
            }
            ps[1] = 0;

            for (int i = 2; i < ps.Length; i++)
            {
                for (int j = 2 * i; j < ps.Length; j += i)
                {
                    ps[j] = 0;
                }
            }

            return ps.Where(x => x >= min).ToArray();
        }
    }
}