【C#】Project Euler 8,9,10問目

はじめに

C#を用いてProjectEulerに挑戦している人の記録です。VisualStudio2017で、1つのフォームアプリの中に問題番号のボタンを作成し、そのボタンをクリックすると結果をラベルに表示するという形式でやっています。

8問目

この1000桁の数字から13個の連続する数字を取り出して, それらの総乗の最大を求めよ

 private void button8_Click(object sender, EventArgs e)
        {
            //この1000桁の数字から13個の連続する数字を取り出して, それらの総乗の最大
            string NumberString1 = "731671765313306249192251196744265747423553491949349698352031277450632623957831801698480" +
                "1869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744" +
                "3043557668966489504452445231617318564030987111217223831136222989342338030813533627661428280644448664523874" +
                "9303589072962904915604407723907138105158593079608667017242712188399879790879227492190169972088809377665727" +
                "3330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977" +
                "8461740649551492908625693219784686224828397224137565705605749026140797296865241453510047482166370484403199" +
                "8900088952434506585412275886668811642717147992444292823086346567481391912316282458617866458359124566529476" +
                "5456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230" +
                "9878799272442849091888458015616609791913387549920052406368991256071760605886116467109405077541002256983155" +
                "20005593572972571636269561882670428252483600823257530420752963450";

            long Number = 1;
            long MaxNumber = 0;
            for (int i = 0; i < NumberString1.Length - 13; i++)
            {
                Number = 1;
                for (int k = 0; k < 13; k++)
                {
                    char c = NumberString1[i + k];
                    Number *= (c - '0');
                }
                if (MaxNumber < Number)
                {
                    MaxNumber = Number;
                }
            }
            label1.Text = "Answer = " + MaxNumber;
        }

1000桁の数字、表示しきれてませんね……。正確な数字は問題を見てみてください。
変数の型から考えて、こんな大きい数字どうやって扱うんだ……。となりましたが、1000桁の数字を文字列として宣言し、そこから13桁取り出して、1文字ずつchar型から数値に変換するという方法を用いました。結果はlong型の大きさに収まりました。

9問目

a + b + c = 1000 となるピタゴラスの三つ組の積abcを求めよ

private void button9_Click(object sender, EventArgs e)
        {
            int a = 0;
            int b = 0;
            int c = 0;

            for (a = 1; a < 1000; a++)
            {
                for (b = 1; b < 1000; b++)
                {
                    for (c = 1; c < 1000; c++)
                    {
                        if (c * c == a * a + b * b)
                        {
                            if (a + b + c == 1000)
                            {
                                long Answer = a * b * c;
                                label1.Text = string.Format("a={0} b={1} c={2} Answer = {3}", a, b, c, Answer);
                                goto ExitLoop;
                            }
                        }
                    }
                }
            }
            ExitLoop:;
        }

a,b,cそれぞれ1000までの全通りを3重ループで試してます。答えが見つかった瞬間にループを抜けて終了しています。C#には2重以上のループを抜ける方法がないので、goto文を用いました。なるべく使わないほうがいいといわれているgoto文ですが、このような場合では使わざるを得ないですね。

10問目

200万以下の全ての素数の和を求めよ

  private void button10_Click(object sender, EventArgs e)
        {
            int Num = 2000000;//リストの最大値
            int[] IntegerList;
            IntegerList = new int[Num];
            var PrimeNumberList = new List<long>();
            var j = 0;
            for (int i = 2; i < Num; i++) { IntegerList[i] = i; }

            int head = 0;
            double EndNum = Math.Sqrt(Num);

            while (head < EndNum)
            {
                //先頭を探す
                for (int i = j; i < Num; i++)
                {
                    if (IntegerList[i] != 0)
                    {
                        head = IntegerList[i];
                        PrimeNumberList.Add(head);
                        j = i;
                        break;
                    }
                }
                //ふるい落とし。落としたものには0を入れる
                foreach (int i in IntegerList)
                {
                    if (IntegerList[i] % head == 0) { IntegerList[i] = 0; }
                }
            }
            for (int a = 2; a < IntegerList.Length; a++)
            {
                if (IntegerList[a] != 0)
                {
                    PrimeNumberList.Add(IntegerList[a]);
                }
            }
            long PrimeSum = 0;
            for (int i = 0; i < PrimeNumberList.Count; i++)
            {
                PrimeSum += PrimeNumberList[i];
            }
            label1.Text = "Answer = " + PrimeSum;
        }

2000000までを配列に格納してエラトステネスの篩をしました。メモリ効率が悪いと考えています。やはり試し割のほうがいいのでしょうか。

おわりに

プログラムの内容よりも、どう解いていくのかが重要になってきているなと感じました。アルゴリズムを考える練習になると思います。