C++实现将素数写成几个素数之和

这个问题可以通过回溯算法来解决。具体的思路是从小到大枚举素数，然后递归地尝试将给定的素数写成几个素数之和的形式。

以下是一个C++实现的示例代码：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }
    int sqrtn = sqrt(n);
    for (int i = 2; i <= sqrtn; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

void write_as_sum_of_primes(int n, vector<int>& factors, vector<vector<int>>& res) {
    if (n == 0) {
        res.push_back(factors);
        return;
    }
    for (int i = 2; i <= n; i++) {
        if (is_prime(i)) {
            if (n >= i) {
                factors.push_back(i);
                write_as_sum_of_primes(n - i, factors, res);
                factors.pop_back();
            } else {
                break;
            }
        }
    }
}

int main() {
    int n;
    cout << "Enter a prime number: ";
    cin >> n;

    vector<int> factors;
    vector<vector<int>> res;

    write_as_sum_of_primes(n, factors, res);

    cout << "The prime number " << n << " can be written as the sum of primes in the following ways: " << endl;
    for (auto& factors : res) {
        cout << n << " = ";
        for (int i = 0; i < factors.size() - 1; i++) {
            cout << factors[i] << " + ";
        }
        cout << factors.back() << endl;
    }

    return 0;
}

这个程序会提示用户输入一个素数，然后输出将该素数写成几个素数之和的所有可能。例如，如果用户输入5，则程序会输出以下结果：

The prime number 5 can be written as the sum of primes in the following ways:
5 = 2 + 3

这个程序的时间复杂度为O(2^n)，因为在最坏情况下，可能需要枚举所有小于等于n的素数的组合。但是，由于素数的个数比较少，实际运行时间很快。