Pongeponge

Project Euler : Problem 50 『Consecutive prime sum』

ゼロの総和 (ハーパーBOOKS)


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

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


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


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


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


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


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


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


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


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


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


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


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


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


 そして再び、ずらし&判定をおこなっていく。
まとまりが素数だと判定されれば、それは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();
        }
    }
}
答え

997651



ゼロの総和 (ハーパーBOOKS)

ゼロの総和 (ハーパーBOOKS)

恐怖の総和〈上〉 (文春文庫)

恐怖の総和〈上〉 (文春文庫)