Count of pairs in an array whose product is a perfect square | C ++ program to calculate the number of pairs with product is perfect square ; Prime [ ] array to calculate Prime Number ; Array k [ ] to store the value of k for each element in arr [ ] ; For value of k , Sieve function is 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 ; Size of arr [ ] ; To pre - compute the value of k ; Function that return total count of pairs with perfect square product
#include <bits/stdc++.h> NEW_LINE using namespace std ; int prime [ 100001 ] = { 0 } ; int k [ 100001 ] = { 0 } ; void Sieve ( ) { for ( int i = 1 ; i < 100001 ; i ++ ) k [ i ] = i ; for ( int i = 2 ; i < 100001 ; i ++ ) { if ( prime [ i ] == 0 ) for ( int j = i ; j < 100001 ; j += i ) { prime [ j ] = 1 ; while ( k [ j ] % ( i * i ) == 0 ) k [ j ] /= ( i * i ) ; } } } int countPairs ( int arr [ ] , int n ) { unordered_map < int , int > freq ; for ( int i = 0 ; i < n ; i ++ ) { freq [ k [ arr [ i ] ] ] ++ ; } int sum = 0 ; for ( auto i : freq ) { sum += ( ( i . second - 1 ) * i . second ) / 2 ; } return sum ; } int main ( ) { int arr [ ] = { 1 , 2 , 4 , 8 , 5 , 6 } ; int n = sizeof ( arr ) / sizeof ( int ) ; Sieve ( ) ; cout << countPairs ( arr , n ) << endl ; return 0 ; }