C#でプロジェクトオイラーを解く（問題５０「連続する素数の和」）

Tweet

Pocket

どーも、みつおです。

やっとレベル２になれた！！！

問題

素数41は6つの連続する素数の和として表せる:

41 = 2 + 3 + 5 + 7 + 11 + 13.

100未満の素数を連続する素数の和で表したときにこれが最長になる.

同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

出典：Problem50

解答

using System;
using System.Collections.Generic;

namespace Problem50
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static long Solve()
        {
            long ret = 0;
            int cnt = 0;
            int sum = 0;
            int max = 0;
            int limit = 1000000;
            List<int> sosulist = new List<int>();

            //素数のリストを作成
            for(int i = 2; i < limit;i++)
            {
                if (IsSosu(i)) sosulist.Add(i);
            }

            for(int i = 0;i < sosulist.Count;i++)
            {
                cnt = 0;
                sum = 0;
                for(int j = i; j < sosulist.Count;j++)
                {
                    //連続する素数の和
                    sum += sosulist[j];

                    //ループを抜ける
                    if (limit < sum) break;

                    //項
                    cnt++;

                    //連続する素数の和が素数か判定
                    var find = sosulist.IndexOf(sum);
                    if(0 < find)
                    {
                        //最大値を更新
                        if (max < cnt)
                        {
                            max = cnt;
                            ret = sum;
                        }
                    }
                }
            }

            return ret;
        }

        private static bool IsSosu(long no)
        {
            bool ret = true;

            //数値が2未満（1)なら素数じゃない、2なら素数
            if (no < 2) return false;
            else if (no == 2) return true;

            //数値が2で割り切れるなら素数じゃない
            if (no % 2 == 0) return false;

            //合成数xはp≦√xを満たす素因子pをもつ
            double sqrtno = Math.Sqrt(no);

            //奇数でループ 
            for (int i = 3; i <= sqrtno; i += 2)
            {
                //割り切れるので素数じゃない
                if (no % i == 0) return false;
            }

            return ret;
        }
    }
}

出力

997651