Count pairs from an array with even product of count of distinct prime factors | Python 3 implementation of the above approach ; Function to calculate count of distinct prime factors of a number ; Sieve of Eratosthenes ; Function to count pairs with even product of distinct prime factors ; Stores count of distinct prime factors ; Stores the count of numbers with even prime factors in B [ ] ; Stores the count of numbers with odd prime factors in B [ ] ; Even Product Pairs ; Traverse the array B [ ] ; Since , product has to be positive i . e > 0 ; If count of prime factors is odd ; Increment oddCount by 1 ; Increment evenCount by 1 ; Since , product has to be positive i . e > 0 ; If count of prime factors is odd ; odd * even = even ; If count of prime factors is even ; even * odd = even even * even = even ; Driver Code
MAX = 1000000 NEW_LINE def countOfPrimefactors ( CountDistinct ) : NEW_LINE INDENT global MAX NEW_LINE prime = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE for i in range ( MAX + 1 ) : NEW_LINE INDENT CountDistinct [ i ] = 0 NEW_LINE prime [ i ] = True NEW_LINE DEDENT for i in range ( 2 , MAX + 1 , 1 ) : NEW_LINE INDENT if ( prime [ i ] == True ) : NEW_LINE INDENT CountDistinct [ i ] = 1 NEW_LINE for j in range ( i * 2 , MAX + 1 , i ) : NEW_LINE INDENT CountDistinct [ j ] += 1 NEW_LINE prime [ j ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT def CountEvenPair ( A , B , N , M ) : NEW_LINE INDENT global MAX NEW_LINE countDistinct = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE countOfPrimefactors ( countDistinct ) NEW_LINE evenCount = 0 NEW_LINE oddCount = 0 NEW_LINE evenPairs = 0 NEW_LINE for i in range ( M ) : NEW_LINE INDENT if ( countDistinct [ B [ i ] ] == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( countDistinct [ B [ i ] ] & 1 ) : NEW_LINE INDENT oddCount += 1 NEW_LINE DEDENT else : NEW_LINE INDENT evenCount += 1 NEW_LINE DEDENT DEDENT for i in range ( N ) : NEW_LINE INDENT if ( countDistinct [ A [ i ] ] == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( countDistinct [ A [ i ] ] & 1 ) : NEW_LINE INDENT evenPairs += ( evenCount ) NEW_LINE DEDENT else : NEW_LINE INDENT evenPairs += evenCount + oddCount NEW_LINE DEDENT DEDENT return evenPairs NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 1 , 2 , 3 ] NEW_LINE B = [ 4 , 5 , 6 ] NEW_LINE N = len ( A ) NEW_LINE M = len ( B ) NEW_LINE print ( CountEvenPair ( A , B , N , M ) ) NEW_LINE DEDENT