Count of subsequences which consists exactly K prime numbers | Returns factorial of n ; Function to return total number of combinations ; Function check whether a number is prime or not ; Corner case ; Check from 2 to n - 1 ; Function for finding number of subsequences which consists exactly K primes ; If number of primes are less than k ; Driver code
def fact ( n ) : NEW_LINE INDENT res = 1 ; NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT res = res * i NEW_LINE DEDENT return res NEW_LINE DEDENT def nCr ( n , r ) : NEW_LINE INDENT return ( fact ( n ) // ( fact ( r ) * fact ( n - r ) ) ) NEW_LINE DEDENT def isPrime ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT for i in range ( 2 , n ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def countSubsequences ( arr , n , k ) : NEW_LINE INDENT countPrime = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( isPrime ( arr [ i ] ) ) : NEW_LINE INDENT countPrime += 1 NEW_LINE DEDENT DEDENT if ( countPrime < k ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return ( nCr ( countPrime , k ) * pow ( 2 , ( n - countPrime ) ) ) NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] NEW_LINE K = 3 NEW_LINE n = len ( arr ) NEW_LINE print ( countSubsequences ( arr , n , K ) ) NEW_LINE