Count of pairs in an array whose product is a perfect square | prime [ ] array to calculate Prime Number ; Array to store the value of k for each element in arr [ ] ; For value of k , Sieve implemented ; Initialize k [ i ] to i ; Prime sieve ; If i is prime then remove all factors of prime from it ; Update that j is not prime ; Remove all square divisors i . e if k [ j ] is divisible by i * i then divide it by i * i ; Function that return total count of pairs with perfect square product ; Map used to store the frequency of k ; Store the frequency of k ; The total number of pairs is the summation of ( fi * ( fi - 1 ) ) / 2 ; Driver code ; Length of arr ; To pre - compute the value of k ; Function that return total count of pairs with perfect square product
prime = [ 0 ] * 100001 NEW_LINE k = [ 0 ] * 100001 NEW_LINE def Sieve ( ) : NEW_LINE INDENT for i in range ( 1 , 100001 ) : NEW_LINE INDENT k [ i ] = i NEW_LINE DEDENT for i in range ( 2 , 100001 ) : NEW_LINE INDENT if ( prime [ i ] == 0 ) : NEW_LINE INDENT for j in range ( i , 100001 , i ) : NEW_LINE INDENT prime [ j ] = 1 NEW_LINE while ( k [ j ] % ( i * i ) == 0 ) : NEW_LINE INDENT k [ j ] /= ( i * i ) NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def countPairs ( arr , n ) : NEW_LINE INDENT freq = dict ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if k [ arr [ i ] ] in freq . keys ( ) : NEW_LINE INDENT freq [ k [ arr [ i ] ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT freq [ k [ arr [ i ] ] ] = 1 NEW_LINE DEDENT DEDENT Sum = 0 NEW_LINE for i in freq : NEW_LINE INDENT Sum += ( freq [ i ] * ( freq [ i ] - 1 ) ) / 2 NEW_LINE DEDENT return Sum NEW_LINE DEDENT arr = [ 1 , 2 , 4 , 8 , 5 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE Sieve ( ) NEW_LINE print ( int ( countPairs ( arr , n ) ) ) NEW_LINE