Các số nguyên tố sau số nguyên tố P có tổng S trong C++

Trong bài toán này, chúng ta được cho ba số: tổng S, số nguyên tố P, và N. Nhiệm vụ là tìm tất cả N số nguyên tố lớn hơn P có tổng bằng S.

Hãy xem ví dụ sau để hiểu rõ vấn đề:

Input: N = 2, P = 5, S = 18 Output: 7 11 Giải thích: Các số nguyên tố lớn hơn 5: 7 11 13 Tổng = 7 + 11 = 18

Để giải quyết, ta phải tìm tất cả các số nguyên tố giữa P và S. Sau đó tìm N số nguyên tố có tổng bằng S. Ta sử dụng kỹ thuật quay lui (backtracking).

Chương trình minh họa triển khai giải pháp:

Ví dụ

#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<<" Số nguyên tố lớn hơn "<<P<<" với tổng = "<<S<<" là :\n";    PrimesWithSum(N, S, P);    return 0; }

Kết quả

3 Số nguyên tố lớn hơn 3 với tổng = 23 là : 5   7   11