任意の偶数を2つの素数の和で表現するアルゴリズムの解説

偶数と素数の和の関係

4以上のすべての偶数は、2つの素数の和として表すことができます。これは有名な「ゴールドバッハ予想」に関連する性質で、1つの偶数に対して複数の素数の組み合わせが存在する場合もあります。

例えば、10という数値は次のように表せます。

• 10 = 5 + 5
• 10 = 7 + 3

本記事で紹介するアルゴリズムは、与えられた偶数に対して、その数を構成できるすべての素数の和の組み合わせを見つけ出します。基本的な考え方はシンプルで、ある数 x が素数であるときに限り、(対象の数 − x) も素数かどうかを判定します。両方が素数であれば、「x + (対象の数 − x)」がその偶数を表す組み合わせとなります。

入力と出力の例

Input:
Even number: 70
Output:
Prime sums
70 = 3 + 67
70 = 11 + 59
70 = 17 + 53
70 = 23 + 47
70 = 29 + 41

アルゴリズム

dispPrimeSum(num)

入力： 偶数。

出力： 素数の和として表現された結果を表示します。

処理の手順

Begin
    if num is odd, then
        exit
    for i := 3 to num/2, do
        if i is prime, then
            if (num - i) is prime, then
                display ''num = i + (num – i)''
    done
End

まず、入力された数が奇数の場合は処理を終了します。次に、3から対象の数の半分まで順番に i を走査し、i が素数であり、かつ (num − i) も素数である場合に、その組み合わせを出力します。探索範囲を半分までに限定することで、重複した組み合わせ（順序が入れ替わっただけのもの）を避けることができます。

C++による実装例

#include<iostream>
using namespace std;

int isPrime(int number) {         //numberが素数かどうかを判定
    int lim;
    lim = number/2;

    for(int i = 2; i<=lim; i++) {
        if(number % i == 0)
            return 0;             //素数ではない
    }
    return 1;                     //素数である
}

void displayPrimeSum(int num) {
    string res;
    if(num%2 != 0) {              //奇数の場合
        cout << "Invalid Number";
        exit(1);
    }

    for(int i = 3; i <= num/2; i++) {
        if(isPrime(i)) {          //iが素数ならば
            if(isPrime(num-i)) {  //num - iも素数であれば
                cout << num <<"= "<<i << " + "<<(num-i)<<endl;
            }
        }
    }
}

main() {
    int num;
    cout << "Enter an even number: "; cin >> num;
    displayPrimeSum(num);
}

コードのポイント

• isPrime関数： 2から number/2 までの整数で割り切れるかを確認し、素数判定を行います。
• displayPrimeSum関数： 奇数が入力された場合は「Invalid Number」と表示して終了し、偶数であれば3から num/2 までの範囲で素数のペアを探します。

実行結果

Enter an even number: 70
70 = 3 + 67
70 = 11 + 59
70 = 17 + 53
70 = 23 + 47
70 = 29 + 41

このように、70を2つの素数の和で表す組み合わせがすべて出力されます。計算量は素数判定の部分で O(n) となり、全体としては O(n²) 程度ですが、小〜中規模の数値であれば十分に実用的な速度で動作します。より大きな数を扱う場合は、エラトステネスの篩などを用いて事前に素数表を作成すると効率化できます。