C++で整数を最大個数の素数の和として表現する方法

この記事では、「整数 N が与えられたとき、それをできるだけ多くの素数の和として表現する」という問題を扱います。まずは具体的な例を見てみましょう。

入力: N = 7
出力: 2 2 3
説明: 7は「2 + 2 + 3」と表せます。これが最大個数の素数による表現です。

入力: N = 17
出力: 2 2 2 2 2 2 2 3

解法のアプローチ

数を素数の和で表す方法として、N からある素数を引き、その差が素数になっているかを確認するアプローチが考えられます。差が素数であれば、N は2つの素数の和として表せることになります。

しかし今回は「最大個数」の素数で表現する必要があるため、最も小さい素数である2と3に着目します。実は、どんな整数でも2と3の和だけで構成することができます。

• Nが偶数の場合： 2を N/2 個加えることで表現できます。

• Nが奇数の場合： 3を1つと、2を (N-3)/2 個組み合わせることで表現できます。

• この方法により、N を最大個数の素数の和として表現できます。

これが最大個数になる理由は、使う素数が小さいほど個数を多くできるからです。素数の中で最小のものは2、次に小さいのは3なので、可能な限り2を使い、奇数の場合にのみ3を1つ使うのが最適な戦略となります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N = 7;
    // Nが奇数かどうかを判定し、
    // 奇数なら「3 +」を出力してNから3を引く
    if (N & 1 == 1) {
        cout << "3 +";
        N -= 3;
    }
    // Nが2になるまで2を出力しながら引いていく
    while (N != 2) {
        cout << " 2 +";
        N -= 2;
    }
    cout << " 2";
    return 0;
}

出力結果

3 + 2 + 2

注意点

Nが非常に小さい場合（例えば N = 3）には上記のループが正しく動作しないため、実際に利用する際は N = 2 や N = 3 といった境界ケースを別途処理することをおすすめします。また、N = 1 はそもそも素数の和では表現できない点にも注意してください。

まとめ

このチュートリアルでは、整数を最大個数の素数の和として表現する問題を取り上げました。最小の素数である2と3に着目するだけで、非常にシンプルなアルゴリズムでこの問題を解決できることを確認しました。紹介したC++プログラムは、C言語、Java、Pythonなど他のプログラミング言語でも同様の考え方で実装可能です。皆さんの学習の一助となれば幸いです。