#include <iostream>
#include <vector>
bool isPrime(int x) {
if (x < 2) return false; // numbers below 2 are not prime
if (x == 2) return true; // 2 is the only even prime
if (x % 2 == 0) return false; // any other even number is not prime
// check odd divisors up to sqrt(x)
for (int i = 3; i * i <= x; i += 2)
if (x % i == 0) return false; // divisible → not prime
return true; // no divisors found → prime
}
// Depth‑first search to find all combinations of primes that sum to 'target'
void explore_all_possibilitie(int target, const std::vector<int>& primes, int idx,
std::vector<int>& current, std::vector<std::vector<int>>& result) {
// If target reaches 0, we found a valid combination
if (target == 0) {
result.push_back(current); // store the combination
return;
}
// Try all primes starting from index 'idx'
// This ensures combinations are non‑decreasing (avoids duplicates)
for (int i = idx; i < (int)primes.size(); ++i) {
int p = primes[i];
if (p > target) break; // no need to continue if prime is too large
current.push_back(p); // choose this prime
explore_all_possibilitie(target - p, primes, i, current, result);
// recurse with reduced target
// 'i' allows reuse of the same prime (e.g., 2+2+2...)
current.pop_back(); // backtrack: remove last added prime
}
}
int main() {
int n = 10; // number we want to express as a sum of primes
// Generate all primes up to n
std::vector<int> primes;
for (int i = 2; i <= n; ++i)
if (isPrime(i)) primes.push_back(i);
std::vector<std::vector<int>> result; // stores all valid combinations
std::vector<int> current; // current combination being built
explore_all_possibilitie(n, primes, 0, current, result);
std::cout << "Number of ways: " << result.size() << "\n";
// Print each combination
for (auto &comb : result) {
for (int i = 0; i < (int)comb.size(); ++i) {
if (i) std::cout << " + "; // print plus sign between numbers
std::cout << comb[i];
}
std::cout << "\n";
}
}
/*
run:
Number of ways: 5
2 + 2 + 2 + 2 + 2
2 + 2 + 3 + 3
2 + 3 + 5
3 + 7
5 + 5
*/
