ゴールドバッハの予想

「ゴールドバッハの予想」とは、次のようなものです。

４以上の偶数は２つの素数の和であらわすことができる

4 = 2 + 2 ですから、これを言い直すと、

6以上の偶数は２つの素数の和であらわすことができる。

とも言えます。

この問題は、数学の未解決問題の一つとして知られてて、1742年に数学者・ゴールドバッハがオイラー宛ての手紙の中で

５よりも大きい自然数は３つの素数の和であらわすことができる。

と予想したことから来ています。

なぜこの予想と最初の予想が、同値であるのかという証明は、Webで検索するといろんなページがヒットしますので、そちらを参照してください。

どんなプログラムにするか

6,8,10.... とすべてを調べるのは時間がかかるので、入力された6以上の偶数(longまでの値)が、「２つの素数の和であらわすことができ」かを確認するプログラムとします。

C#のコード

以下に、C#のコード(コンソールアプリ)を示します。

Goldbach.cs

class Program {
    static void Main(string[] args) {
        while (true) {
            var str = Console.ReadLine();
            long num;
            if (long.TryParse(str, out num) == false) {
                Console.Error.WriteLine("入力形式が異なります。6以上の偶数を入力してください。");
            } else if (num % 2 != 0 || num < 6) {
                Console.Error.WriteLine("6以上の偶数を入力してください。");
            } else {
                var r = Goldbach.Resolve(num);
                Console.WriteLine($"{num} = {r[0]} + {r[1]}");
            }
        }
    }
}

public static class Goldbach {

    public static long[] Resolve(long num) {
        for (long a = 3; a <= num; a += 2) {
            if (!PrimeNumber.IsPrime(a))
                continue;
            long b = num - a;
            if (PrimeNumber.IsPrime(b))
                return new long[] { a, b };
        }
        return new long[] { -1, -1 };
    }
}

ほんの少しコードの補足説明

Goldbach.Resolveメソッドでは、２つの素数を返すところで、

return new long[] { a, b };

と配列を返しています。
2つのプロパティを持つ専用のクラスを定義するよりもこの方が簡単です。
Tuple¹ を戻り値にする方法もありますが、無味乾燥なItem1, Item2という名前がどうも好きになれません。

PrimeNumber.IsPrimeは、「C#:ミラー・ラビン素数判定法を使い素数判定メソッドを書いてみた」で示した、メソッドを利用しています。

課題

例えば、「6以上、1000万までの偶数は２つの素数の和であらわすことができるか」を調べるという問題だとすると、僕のPCだと１分くらいでした。それなりの速度が出ていると思います。しかし、検証する範囲をさらに拡大しようとした場合、このプログラムだとちょっと苦しいかなと感じます。並列処理するようなプログラムにする必要があるかもしれません。

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。

C#7.0でこの状況は改善されそうなので、期待しています。 ↩