Count of all subsequence whose product is a Composite number | Function to check whether a number is prime or not ; Function to find number of subsequences whose product is a composite number ; Find total non empty subsequence ; Find count of prime number and ones ; Calculate the non empty one subsequence ; Find count of composite subsequence ; Driver code
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 ) : NEW_LINE INDENT totalSubsequence = ( int ) ( pow ( 2 , n ) - 1 ) ; NEW_LINE countPrime = 0 ; NEW_LINE countOnes = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] == 1 ) : NEW_LINE INDENT countOnes += 1 ; NEW_LINE DEDENT elif ( isPrime ( arr [ i ] ) ) : NEW_LINE INDENT countPrime += 1 ; NEW_LINE DEDENT DEDENT compositeSubsequence = 0 ; NEW_LINE onesSequence = ( int ) ( pow ( 2 , countOnes ) - 1 ) ; NEW_LINE compositeSubsequence = ( totalSubsequence - countPrime - onesSequence - onesSequence * countPrime ) ; NEW_LINE return compositeSubsequence ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 1 , 2 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( countSubsequences ( arr , n ) ) ; NEW_LINE DEDENT