C++で合計がNに等しくなる素数の最大個数を求める方法

問題の概要

この問題では、整数 N が与えられ、その合計がちょうど N に等しくなるような素数の最大個数を求めることを目標とします。

まず前提として、素数とは 1 とその数自身でしか割り切れない正の整数のことです。たとえば 2、3、5、7、11 などが該当します。

具体的な例を見てみましょう。

入力： N = 9

出力： 4

説明：

9 は以下のように素数の和として表すことができます：
2 + 2 + 2 + 3 = 9（4個）
3 + 3 + 3 = 9（3個）
2 + 2 + 5 = 9（3個）
2 + 7 = 9（2個）
この中で最も多くの素数を使用しているのは「2, 2, 2, 3」の4個です。

解き方のアプローチ

使用する素数の個数を最大化するには、できるだけ小さい素数を何度も足し合わせるのが最適な戦略になります。

最小の素数は 2 であり、次に小さい素数は 3（奇数） です。したがって、合計の計算には 2 と 3 のみを使うことで個数を最大化できます。

この考え方をもとに、問題は次の2つの場合に分けて考えることができます。

ケース1：N が偶数の場合

合計に使われる素数はすべて 2 になります。よって答えは N / 2 です。

ケース2：N が奇数の場合

合計に使われる素数は、1つだけ 3 を使い残りはすべて 2 になります。よって答えは (N - 1) / 2 です。

実は、C++ の整数除算では切り捨てが行われるため、奇数・偶数どちらの場合でも単純に n / 2 を返すだけで両方のケースをカバーできます。奇数の場合、n / 2 は自動的に (n - 1) / 2 と同じ結果になるからです。

C++での実装例

以下は、合計が N に等しくなる素数の最大個数を求める C++ プログラムです。

#include <iostream>
using namespace std;

int maxPrimeCount(int n){
    // 奇数の場合も含めて、n/2 が常に答えとなる
    // （偶数：すべて2の個数、奇数：1つの3と残り2の個数）
    return n / 2;
}

int main(){
    int n = 9;
    cout << "合計が " << n << " に等しくなる素数の最大個数は "
         << maxPrimeCount(n) << " です";
    return 0;
}

出力結果

合計が 9 に等しくなる素数の最大個数は 4 です

計算量について

このアルゴリズムは単純な除算のみで構成されているため、時間計算量は O(1)、空間計算量も O(1) ときわめて効率的です。大きな N が与えられても即座に答えを求められます。

まとめ

合計が N に等しくなる素数の最大個数を求める問題は、「最小の素数である 2 をできるだけ多く使い、奇数の場合は 3 を 1 つ加える」というシンプルな発想で解決できます。数学的な考察により、答えは常に N / 2（整数除算）となることが証明できるため、複雑な探索や動的計画法を使わずとも定数時間で処理可能です。