Count of pairs in an array whose product is a perfect square | Java 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
import java . util . * ; class GFG { static int [ ] prime = new int [ 100001 ] ; static int [ ] k = new int [ 100001 ] ; static 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 ) ; } } } static int countPairs ( int arr [ ] , int n ) { HashMap < Integer , Integer > freq = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( freq . containsKey ( k [ arr [ i ] ] ) ) { freq . put ( k [ arr [ i ] ] , freq . get ( k [ arr [ i ] ] ) + 1 ) ; } else freq . put ( k [ arr [ i ] ] , 1 ) ; } int sum = 0 ; for ( Map . Entry < Integer , Integer > i : freq . entrySet ( ) ) { sum += ( ( i . getValue ( ) - 1 ) * i . getValue ( ) ) / 2 ; } return sum ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 4 , 8 , 5 , 6 } ; int n = arr . length ; Sieve ( ) ; System . out . print ( countPairs ( arr , n ) + "NEW_LINE"); } }