C#でプロジェクトオイラーを解く（問題２７「二次式素数」）

Tweet

Pocket

どーも、みつおです。

プロジェクトオイラーって素数の問題がかなり多いよね。

問題

オイラーは以下の二次式を考案している:

n^2 + n + 41.

この式は, n を0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40 のとき 402 + 40 + 41 = 40(40 + 1) + 41 となり41で割り切れる. また, n = 41 のときは 412 + 41 + 41 であり明らかに41で割り切れる.

計算機を用いて, 二次式 n^2 – 79n + 1601 という式が発見できた. これは n = 0 から 79 の連続する整数で80個の素数を生成する. 係数の積は, -79 × 1601 で -126479である.

さて, |a| < 1000, |b| ≤ 1000 として以下の二次式を考える (ここで |a| は絶対値): 例えば |11| = 11 |-4| = 4である.

n^2 + an + b

n = 0 から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数 a, b の積を答えよ.

出典：Problem27

解答

using System;

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

        private static long Solve()
        {
            long ret = 0;
            long cnt = 0;

            //係数 a のループ
            for (int a = -999; a < 1000; a++)
            {
                //係数 b のループ
                for(int b = -1000; b <= 1000; b++)
                {
                    //係数 n のループ
                    for(int n = 0; n < int.MaxValue; n++)
                    {
                        //素数判定
                        if (IsSosu(n * n + a * n + b))
                        {
                            //連続の最大値判定
                            if (cnt < n)
                            {
                                cnt = n;
                                ret = a * b;
                            }
                        }
                        else break;
                    }
                }
            }

            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;

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

            return ret;
        }
    }
}

出力

-59231