Count of pairs in an array whose product is a 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
let prime = new Array ( 100001 ) . fill ( 0 ) ; let k = new Array ( 100001 ) . fill ( 0 ) ; function Sieve ( ) { for ( let i = 1 ; i < 100001 ; i ++ ) k [ i ] = i ; for ( let i = 2 ; i < 100001 ; i ++ ) { if ( prime [ i ] == 0 ) for ( let j = i ; j < 100001 ; j += i ) { prime [ j ] = 1 ; while ( k [ j ] % ( i * i ) == 0 ) k [ j ] /= ( i * i ) ; } } } function countPairs ( arr , n ) { let freq = new Map ( ) ; for ( let i = 0 ; i < n ; i ++ ) { if ( freq . has ( k [ arr [ i ] ] ) ) { freq . set ( k [ arr [ i ] ] , freq . get ( k [ arr [ i ] ] ) + 1 ) ; } else freq . set ( k [ arr [ i ] ] , 1 ) ; } let sum = 0 ; for ( let i of freq ) { sum += ( ( i [ 1 ] - 1 ) * i [ 1 ] ) / 2 ; } return sum ; } let arr = [ 1 , 2 , 4 , 8 , 5 , 6 ] ; let n = arr . length ; Sieve ( ) ; document . write ( countPairs ( arr , n ) + " " ) ;