C++で合計がSとなる、素数Pより大きいN個の素数を見つける方法

問題概要

この問題では、3つの値――合計 S、素数 P、そして個数 N ――が与えられます。求めるのは、「P より大きい素数の中から N 個を選び、その合計がちょうど S になるような組み合わせ」をすべて見つけることです。

入出力例

Input: N = 2, P = 5, S = 18
Output: 7 11
Explanation: 5より大きい素数 : 7 11 13
Sum = 7 + 11 = 18

この例では、5 より大きい素数は「7, 11, 13」ですが、その中で合計が 18 になるのは「7 + 11」の組み合わせだけであることがわかります。

解法のアプローチ

まず、P と S の間に存在するすべての素数を列挙します。その後、バックトラッキング(試行錯誤しながら条件に合わない経路を切り捨てる探索手法)を使って、合計が S になる N 個の素数の組み合わせを探します。

具体的な手順は以下の通りです。

1. P+1 から S までの範囲にある素数をすべて収集する
2. 収集した素数リストに対して再帰的にバックトラッキングを実行する
3. 各ステップで「現在の素数を採用する」「採用しない」の2通りの分岐を試す
4. 合計が S になり、選んだ素数の個数が N に達した時点で、その組み合わせを出力する

C++による実装例

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> set;
vector<int> primeNo;
bool isPrimeNumber(int x) {
    int sqroot = sqrt(x);
    bool flag = true;
    if (x == 1)
        return false;
    for (int i = 2; i <= sqroot; i++)
        if (x % i == 0)
            return false;
    return true;
}
void printPrimes() {
    int length = set.size();
    for (int i=0; i<length; i++)
        cout<<set[i]<<"\t";
    cout<<endl;
}
void GeneratePrimeSum(int total, int N, int S, int index) {
    if (total == S && set.size() == N) {
        printPrimes();
        return;
    }
    if (total > S || index == primeNo.size())
        return;
    set.push_back(primeNo[index]);
    GeneratePrimeSum(total+primeNo[index], N, S, index+1);
    set.pop_back();
    GeneratePrimeSum(total, N, S, index+1);
}
void PrimesWithSum(int N, int S, int P) {
    for (int i = P+1; i <=S ; i++) {
        if (isPrimeNumber(i))
            primeNo.push_back(i);
    }
    if (primeNo.size() < N)
        return;
    GeneratePrimeSum(0, N, S, 0);
}
int main() {
    int S = 23, N = 3, P = 3;
    cout<<N<<" Prime numbers greater than "<<P<<" with sum = "<<S<<" are :\n";
    PrimesWithSum(N, S, P);
    return 0;
}

コードのポイント

• isPrimeNumber(): 2 から平方根まで順に割っていく試し割り法で素数判定を行います。
• GeneratePrimeSum(): バックトラッキングの本体です。現在の素数をセットに追加して再帰呼び出しを行い、戻った後に取り除いて(バックトラックして)次の候補へ進みます。
• PrimesWithSum(): 素数の収集とバックトラッキングの開始をまとめて処理する関数です。候補となる素数の総数が N 未満の場合は解が存在しないため、即座に終了します。

実行結果

3 Prime numbers greater than 3 with sum = 23 are :
5   7   11

この例では、3 より大きい素数「5, 7, 11」の3つを選ぶと、合計は 5 + 7 + 11 = 23 となり、条件を満たしていることが確認できます。