Count of all subsequence whose product is a Composite number | Java implementation to count all subsequence whose product is 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
import java . util . * ; class GFG { static boolean isPrime ( int n ) { if ( n <= 1 ) return false ; for ( int i = 2 ; i < n ; i ++ ) if ( n % i == 0 ) return false ; return true ; } static int countSubsequences ( int arr [ ] , int n ) { int totalSubsequence = ( int ) ( Math . pow ( 2 , n ) - 1 ) ; int countPrime = 0 , countOnes = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] == 1 ) countOnes ++ ; else if ( isPrime ( arr [ i ] ) ) countPrime ++ ; } int compositeSubsequence ; int onesSequence = ( int ) ( Math . pow ( 2 , countOnes ) - 1 ) ; compositeSubsequence = totalSubsequence - countPrime - onesSequence - onesSequence * countPrime ; return compositeSubsequence ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 1 , 2 } ; int n = arr . length ; System . out . print ( countSubsequences ( arr , n ) ) ; } }