Count pairs in an array whose product is composite number | Python3 program to implement the above approach ; Function to get all the prime numbers in the range [ 1 , X ] ; Stores the boolean value to check if a number is prime or not ; Mark all non prime numbers as false ; If i is prime number ; Mark j as a composite number ; Function to get the count of pairs whose product is a composite number ; Stores the boolean value to check if a number is prime or not ; Stores the count of 1 s ; Stores the count of prime numbers ; Traverse the given array . ; Stores count of pairs whose product is not a composite number ; Stores the count of pairs whose product is composite number ; Driver Code
X = 1000000 NEW_LINE def getPrimeNum ( ) : NEW_LINE INDENT isPrime = [ True ] * ( X ) NEW_LINE isPrime [ 0 ] = False NEW_LINE isPrime [ 1 ] = False NEW_LINE i = 2 NEW_LINE while i * i <= X : NEW_LINE INDENT if ( isPrime [ i ] == True ) : NEW_LINE INDENT for j in range ( i * i , X , i ) : NEW_LINE INDENT isPrime [ j ] = False NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT return isPrime NEW_LINE DEDENT def cntPairs ( arr , N ) : NEW_LINE INDENT isPrime = getPrimeNum ( ) NEW_LINE cntOne = 0 NEW_LINE cntPrime = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( arr [ i ] == 1 ) : NEW_LINE INDENT cntOne += 1 NEW_LINE DEDENT elif ( isPrime [ i ] ) : NEW_LINE INDENT cntPrime += 1 NEW_LINE DEDENT DEDENT cntNonComp = 0 NEW_LINE cntNonComp = ( cntPrime * cntOne + cntOne * ( cntOne - 1 ) // 2 ) NEW_LINE res = 0 NEW_LINE res = ( N * ( N - 1 ) // 2 - cntNonComp ) NEW_LINE return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 1 , 2 , 2 , 8 ] NEW_LINE N = len ( arr ) NEW_LINE print ( cntPairs ( arr , N ) ) NEW_LINE DEDENT