Minimum number of single digit primes required whose sum is equal to N in C++

Problem statement

Find the minimum number of single-digit prime numbers required whose sum will be equal to N.

Example

If N = 9 then we require 2 prime numbers i.e. 7 and 2 to make sum 9.

Example

#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; }

Output

When you compile and execute above program. It generates following output −

Minimum required primes: 2