Count of elements to be multiplied with integers to make each pair of Array a perfect square | Java program for the above approach ; Function to find the smallest prime factor of the elements ; Initializing the first element of the array ; Loop to add the remaining elements to the array ; Marking the smallest prime factor for every number to be itself ; Separately marking spf for every even number as 2 ; Checking if i is prime ; Marking SPF for all the numbers divisible by i ; Marking spf [ j ] if it is not previously marked ; Function to find the minimum number of steps to modify the array such that the product of any two numbers in the array is a perfect square ; Map created to store the unique prime numbers ; Variable to store the minimum number of operations ; Loop to store every unique prime number ; Erasing 1 as a key because it is not a prime number ; Iterating through the hash ; Two variables used for counting the frequency of prime is even or odd ; First prime number ; Iterating the number D ; Check if prime is a factor of the element in the array ; Loop for calculating the frequency of the element ; Check for frequency odd or even ; If it is not a factor of the element , then it is automatically even ; Storing the minimum of two variable even or odd ; Driver Code ; Input array ; Creating shortest prime factorisation array
import java . io . * ; import java . util . * ; class GFG { static void spf_array ( int spf [ ] ) { spf [ 1 ] = 1 ; for ( int i = 2 ; i < 1000 ; i ++ ) spf [ i ] = i ; for ( int i = 4 ; i < 1000 ; i += 2 ) spf [ i ] = 2 ; for ( int i = 3 ; i * i < 1000 ; i ++ ) { if ( spf [ i ] == i ) { for ( int j = i * i ; j < 1000 ; j += i ) if ( spf [ j ] == j ) spf [ j ] = i ; } } } static int minimum_operation ( int b [ ] , int d , int spf [ ] ) { Map < Integer , Integer > m = new HashMap < > ( ) ; int i = 0 ; int c = 0 ; for ( i = 0 ; i < d ; i ++ ) { int x = b [ i ] ; while ( x != 1 ) { x = x / spf [ x ] ; if ( m . get ( spf [ x ] ) == null ) { m . put ( spf [ x ] , 1 ) ; } } } m . remove ( 1 ) ; for ( Map . Entry < Integer , Integer > x : m . entrySet ( ) ) { int e = 0 , o = 0 ; int j = x . getKey ( ) ; for ( i = 0 ; i < d ; i ++ ) { if ( b [ i ] % j == 0 ) { int h = 0 ; int g = b [ i ] ; while ( g != 0 ) { if ( g % j != 0 ) { break ; } g = g / j ; h = h + 1 ; } if ( h % 2 == 0 ) { e = e + 1 ; } else { o = o + 1 ; } } else { e = e + 1 ; } } c = c + Math . min ( o , e ) ; } return c ; } public static void main ( String [ ] args ) { int [ ] spf = new int [ 1001 ] ; int b [ ] = { 1 , 4 , 6 } ; int d = b . length ; spf_array ( spf ) ; System . out . print ( minimum_operation ( b , d , spf ) ) ; } }