C++で合計がNになる1桁の素数の最小個数を求める方法

問題の概要

与えられた整数 N に対して、合計がちょうど N となるように必要な「1桁の素数」の最小個数を求めます。1桁の素数は 2、3、5、7 の4種類のみです。

例

たとえば N = 9 の場合、7 と 2 の2つの素数を足せば合計が 9 になるため、答えは 2 となります。

解き方：動的計画法（DP）

この問題は、いわゆる「コイン問題」とよく似た構造を持っています。合計値を金額、素数をコインと見立てて最小枚数を求めるのと同じ考え方で解くことができます。

配列 arr[i] には「合計 i を作るために必要な素数の最小個数」を格納します。まず到達不可能を表す大きな値で全体を初期化し、arr[0]・arr[2]・arr[3]・arr[5]・arr[7] のみ 1 を設定します。その後、小さい側から順に、2・3・5・7 を引いたインデックスの値に 1 を加えたものと比較しながら最小値を更新していきます。

アルゴリズムの手順

1. サイズ n+1 の配列 arr を用意し、すべての要素を大きな値で初期化する。
2. arr[0]、arr[2]、arr[3]、arr[5]、arr[7] を 1 に設定する。
3. i を 1 から n まで走査し、i−2、i−3、i−5、i−7 が有効なインデックスであれば、arr[i] を min(arr[i], 1 + arr[i − 素数]) で更新する。
4. 最終的に arr[n] が初期値のままなら -1 を返し（合計を作れない）、そうでなければ arr[n] を返す。

C++実装例

#include <iostream>
using namespace std;
bool isValidIndex(int i, int val) {
    return (i - val) < 0 ? false : true;
}
int getMinPrimes(int n) {
    int arr[n + 1];
    for (int i = 1; i <= n; ++i) {
        arr[i] = 1000000000L;
    }
    arr[0] = arr[2] = arr[3] = arr[5] = arr[7] = 1;
    for (int i = 1; i <= n; ++i) {
        if (isValidIndex(i, 2)) {
            arr[i] = min(arr[i], 1 + arr[i - 2]);
        }
        if (isValidIndex(i, 3)) {
            arr[i] = min(arr[i], 1 + arr[i - 3]);
        }
        if (isValidIndex(i, 5)) {
            arr[i] = min(arr[i], 1 + arr[i - 5]);
        }
        if (isValidIndex(i, 7)) {
            arr[i] = min(arr[i], 1 + arr[i - 7]);
        }
    }
    return arr[n] == 1000000000L ? -1 : arr[n];
}
int main() {
    int n = 9;
    int result = getMinPrimes(n);
    if (result != -1) {
        cout << "Minimum required primes: " << getMinPrimes(n) << endl;
    } else {
        cout << "Not possible to create required sum" << endl;
    }
    return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum required primes: 2

計算量

各インデックスに対して4つの素数を試すだけなので、時間計算量は O(n)、配列1つ分の O(n) の空間計算量で収まります。N が大きくなっても効率的に動作するのが、この動的計画法によるアプローチの利点です。