Count of elements to be multiplied with integers to make each pair of Array a perfect square | 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
function spf_array ( spf ) { spf [ 1 ] = 1 ; for ( var i = 2 ; i < 1000 ; i ++ ) spf [ i ] = i ; for ( var i = 4 ; i < 1000 ; i += 2 ) spf [ i ] = 2 ; for ( var i = 3 ; i * i < 1000 ; i ++ ) { if ( spf [ i ] == i ) { for ( var j = i * i ; j < 1000 ; j += i ) if ( spf [ j ] == j ) spf [ j ] = i ; } } } function minimum_operation ( b , d , spf ) { var m = new Map ( ) ; var i = 0 ; var c = 0 ; for ( i = 0 ; i < d ; i ++ ) { var x = b [ i ] ; while ( x != 1 ) { x = parseInt ( x / spf [ x ] ) ; if ( ! m . has ( spf [ x ] ) ) { m . set ( spf [ x ] , 1 ) ; } } } m . delete ( 1 ) ; m . forEach ( ( value , key ) => { var e = 0 , o = 0 ; var j = key ; for ( i = 0 ; i < d ; i ++ ) { if ( b [ i ] % j == 0 ) { var h = 0 ; var g = b [ i ] ; while ( g != 0 ) { if ( g % j != 0 ) { break ; } g = parseInt ( 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 ; } var spf = Array ( 1001 ) var b = [ 1 , 4 , 6 ] ; var d = b . length ; spf_array ( spf ) ; document . write ( minimum_operation ( b , d , spf ) ) ;