Minimum number of single digit primes required whose sum is equal to N | CPP program to find the minimum number of single digit prime numbers required which when summed equals to a given number N . ; function to check if i - th index is valid or not ; function to find the minimum number of single digit prime numbers required which when summed up equals to a given number N . ; Not possible ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( int i , int val ) { if ( i - val < 0 ) return false ; return true ; } int MinimumPrimes ( int n ) { int dp [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) dp [ i ] = 1e9 ; dp [ 0 ] = dp [ 2 ] = dp [ 3 ] = dp [ 5 ] = dp [ 7 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { if ( check ( i , 2 ) ) dp [ i ] = min ( dp [ i ] , 1 + dp [ i - 2 ] ) ; if ( check ( i , 3 ) ) dp [ i ] = min ( dp [ i ] , 1 + dp [ i - 3 ] ) ; if ( check ( i , 5 ) ) dp [ i ] = min ( dp [ i ] , 1 + dp [ i - 5 ] ) ; if ( check ( i , 7 ) ) dp [ i ] = min ( dp [ i ] , 1 + dp [ i - 7 ] ) ; } if ( dp [ n ] == ( 1e9 ) ) return -1 ; else return dp [ n ] ; } int main ( ) { int n = 12 ; int minimal = MinimumPrimes ( n ) ; if ( minimal != -1 ) cout << " Minimum ▁ number ▁ of ▁ single " << " ▁ digit ▁ primes ▁ required ▁ : ▁ " << minimal << endl ; else cout << " Not ▁ possible " ; return 0 ; }