C++で数値が2つの素数の和として表現できるかを判定する方法

はじめに

この記事では、入力された数値が2つの素数の和として表現できるかどうかを判定するC++プログラムを紹介します。このテーマは、有名な「ゴールドバッハ予想」（4以上のすべての偶数は2つの素数の和で表せるという未解決問題）にも関連しており、素数判定の基礎を学ぶのに最適な題材です。

サンプルコード

#include <iostream>
using namespace std;
int func(int num) {
   int i;
   int flag = 1;
   for(i = 2; i <= num/2; ++i) {
      if(num % i == 0) {
         flag = 0;
         break;
      }
   }
   return flag;
}
int main() {
   int num , i;
   cout << "Enter a number : \n";
   cin >> num;
   for(i = 2; i <= num/2; ++i) {
      if (func(i)) {
         if (func(num - i)) {
            cout << num << " = " << i << " + " << num-i << endl;
         }
      }
   }
   return 0;
}

実行結果

Enter a number : 18
18 = 5 + 13
18 = 7 + 11

この実行例では、18が「5 + 13」と「7 + 11」という2組の素数の組み合わせで表現できたことがわかります。

コードの解説

まず、func()関数は、引数で受け取った数値が素数かどうかを判定する役割を担っています。2からnum/2までの整数で順番に割り算を行い、1つでも割り切れる数が見つかった場合は素数ではないと判断してflagを0にし、そこで処理を打ち切ります。

int func(int num) {
   int i;
   int flag = 1;
   for(i = 2; i <= num/2; ++i) {
      if(num % i == 0) {
         flag = 0;
         break;
      }
   }
   return flag;
}

次に、main()関数では、ユーザーから数値を入力として受け取ります。その後、2からnum/2までの各整数iについて、「i自身が素数」であり、かつ「num − i も素数」であるかをfunc()関数で確認します。両方の条件を満たす場合のみ、その組み合わせを画面に出力します。

cout << "Enter a number : \n";
cin >> num;
for(i = 2; i <= num/2; ++i) {
   if (func(i)) {
      if (func(num - i)) {
         cout << num << " = " << i << " + " << num-i << endl;
      }
   }
}

ループ範囲をnum/2までに限定しているのは、それ以降の組み合わせは単に足す順序が入れ替わっただけの重複になるためです。この工夫によって、無駄のない効率的な探索が可能になります。なお、素数判定の計算量をさらに削減したい場合は、判定範囲を√numまでに狭める方法や、エラトステネスのふるいを活用する方法も検討するとよいでしょう。