Count pairs whose product contains single distinct prime factor | Function to find a single distinct prime factor of N ; Stores distinct prime factors of N ; Calculate prime factor of N ; Calculate distinct prime factor ; Insert i into disPrimeFact ; Update N ; If N is not equal to 1 ; Insert N into disPrimeFact ; If N contains a single distinct prime factor ; Return single distinct prime factor of N ; If N contains more than one distinct prime factor ; Function to count pairs in the array whose product contains only single distinct prime factor ; Stores count of 1 s in the array ; mp [ i ] : Stores count of array elements whose distinct prime factor is only i ; Traverse the array arr [ ] ; If current element is 1 ; Store distinct prime factor of arr [ i ] ; If arr [ i ] contains more than one prime factor ; If arr [ i ] contains a single prime factor ; Stores the count of pairs whose product of elements contains only a single distinct prime factor ; Traverse the map mp [ ] ; Stores count of array elements whose prime factor is ( it . first ) ; Update res ; Driver Code
def singlePrimeFactor ( N ) : NEW_LINE INDENT disPrimeFact = { } NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT if i * i > N : NEW_LINE INDENT break NEW_LINE DEDENT while ( N % i == 0 ) : NEW_LINE INDENT disPrimeFact [ i ] = 1 NEW_LINE N //= i NEW_LINE DEDENT DEDENT if ( N != 1 ) : NEW_LINE INDENT disPrimeFact [ N ] = 1 NEW_LINE DEDENT if ( len ( disPrimeFact ) == 1 ) : NEW_LINE INDENT return list ( disPrimeFact . keys ( ) ) [ 0 ] NEW_LINE DEDENT return - 1 NEW_LINE DEDENT def cntsingleFactorPair ( arr , N ) : NEW_LINE INDENT countOf1 = 0 NEW_LINE mp = { } NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( arr [ i ] == 1 ) : NEW_LINE INDENT countOf1 += 1 NEW_LINE continue NEW_LINE DEDENT factorValue = singlePrimeFactor ( arr [ i ] ) NEW_LINE if ( factorValue == - 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT else : NEW_LINE INDENT mp [ factorValue ] = mp . get ( factorValue , 0 ) + 1 NEW_LINE DEDENT DEDENT res = 0 NEW_LINE for it in mp : NEW_LINE INDENT X = mp [ it ] NEW_LINE res += countOf1 * X + ( X * ( X - 1 ) ) // 2 NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 ] NEW_LINE N = len ( arr ) NEW_LINE print ( cntsingleFactorPair ( arr , N ) ) NEW_LINE DEDENT