Minimum number of single digit primes required whose sum is equal to 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
def check ( i , val ) : NEW_LINE INDENT if i - val < 0 : NEW_LINE INDENT return False NEW_LINE DEDENT return True NEW_LINE DEDENT def MinimumPrimes ( n ) : NEW_LINE INDENT dp = [ 10 ** 9 ] * ( n + 1 ) NEW_LINE dp [ 0 ] = dp [ 2 ] = dp [ 3 ] = dp [ 5 ] = dp [ 7 ] = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if check ( i , 2 ) : NEW_LINE INDENT dp [ i ] = min ( dp [ i ] , 1 + dp [ i - 2 ] ) NEW_LINE DEDENT if check ( i , 3 ) : NEW_LINE INDENT dp [ i ] = min ( dp [ i ] , 1 + dp [ i - 3 ] ) NEW_LINE DEDENT if check ( i , 5 ) : NEW_LINE INDENT dp [ i ] = min ( dp [ i ] , 1 + dp [ i - 5 ] ) NEW_LINE DEDENT if check ( i , 7 ) : NEW_LINE INDENT dp [ i ] = min ( dp [ i ] , 1 + dp [ i - 7 ] ) NEW_LINE DEDENT DEDENT if dp [ n ] == 10 ** 9 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return dp [ n ] NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 12 NEW_LINE minimal = MinimumPrimes ( n ) NEW_LINE if minimal != - 1 : NEW_LINE INDENT print ( " Minimum ▁ number ▁ of ▁ single ▁ digit ▁ primes ▁ required ▁ : ▁ " , minimal ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ possible " ) NEW_LINE DEDENT DEDENT