【C#】Project Euler 5,6,7問目

はじめに

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

5問目

1 から 20 までの整数全てで割り切れる数字の中で最小の正の数を求めよ

 public static long Gcd(long a, long b)
        {
            if (a < b)
            {
                return Gcd(b, a);
            }
            else
            {
                while (b != 0)
                {
                    var tmp = a % b;
                    a = b;
                    b = tmp;
                }
                return a;
            }
        }
public static long lcm(long a, long b)
        {
            return (a * b) / Gcd(a, b);
        }
private void button5_Click(object sender, EventArgs e)
        {
            long i;
            long n = 1;
            for (i = 1; i <= 20; i++)
            {
                n = lcm(n, i);
            }
            label1.Text = "Answer= " + n;
        }

1から20までのLCM（最小公倍数）を求めます。1から20で割り切れるということはその倍数であり、その最小を求めるためです。ユークリッドの互除法でGCD（最小公約数）を求めると、そこからLCMが求まります。

6問目

最初の100個の自然数について二乗の和と和の二乗の差を求めよ

private void button6_Click(object sender, EventArgs e)
        {
            //最初の100個の自然数について二乗の和と和の二乗の差
            int n = 100;
            int Sum = (n * (n + 1)) / 2;
            int SumSquare = Sum * Sum;
            int SquareSum = (n * (n + 1) * (2 * n + 1)) / 6;
            int Answer = SumSquare - SquareSum;
            label1.Text = "Answer = " + Answer;
        }

和の公式を用いました。1から100までの和を2乗し、2乗の和から引きました。

7問目

10001番目の素数を求めよ

 private void button7_Click(object sender, EventArgs e)
        {
            int Num = 1000000;//リストの最大値
            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]);
                }
            }
            label1.Text = "Answer = " + PrimeNumberList[10000];
        }

エラトステネスの篩を用いています。1から1000000までが入ったリストを作り、エラトステネスの篩でふるい落とされた要素には0を代入し、残った数字を最後に取り出しています。もっと効率の良いエラトステネスの篩の実装方法があると思います。どうか教えてください......。