C++ में N के बराबर योग के लिए आवश्यक न्यूनतम एक-अंकीय अभाज्य संख्याएँ

समस्या विवरण

उन न्यूनतम एक-अंकीय अभाज्य संख्याओं की संख्या ढूंढें जिनका योग N के बराबर हो।

उदाहरण

यदि N = 9 तो हमें 2 अभाज्य संख्याओं की आवश्यकता है यानी 7 और 2 ताकि योग 9 बने।

उदाहरण

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

आउटपुट

जब आप उपरोक्त प्रोग्राम को कंपाइल और एक्जीक्यूट करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है:

Minimum required primes: 2