Minimum replacement of pairs by their LCM required to reduce given array to its LCM | javascript program for the above approach ; Boolean array to set or unset prime non - prime indices ; Stores the prefix sum of the count of prime numbers ; Function to check if a number is prime or not from 0 to N ; If p is a prime ; Set its multiples as non - prime ; Function to store the count of prime numbers ; Function to count the operations to reduce the array to one element by replacing each pair with its LCM ; Generating Prime Number ; Corner Case ; Stores the prefix sum of the count of prime numbers ; Given array arr ; Function call
const maxm = 10001 ; var prime = Array ( ) ; var prime_number = Array ( ) ; function SieveOfEratosthenes ( ) { for ( i = 0 ; i < maxm ; i ++ ) prime [ i ] = true ; for ( p = 2 ; p * p < maxm ; p ++ ) { if ( prime [ p ] == true ) { for ( i = p * p ; i < maxm ; i += p ) prime [ i ] = false ; } } prime [ 0 ] = false ; prime [ 1 ] = false ; } function num_prime ( ) { prime_number [ 0 ] = 0 ; for ( i = 1 ; i <= maxm ; i ++ ) { var tmp ; if ( prime [ i ] == true ) { tmp = 1 ; } else { tmp = 0 ; } prime_number [ i ] = prime_number [ i - 1 ] + tmp ; } } function min_steps ( arr , n ) { SieveOfEratosthenes ( ) ; num_prime ( ) ; if ( n == 1 ) { document . write ( " " ) ; } else if ( n == 2 ) { document . write ( " " ) ; } else { document . write ( prime_number [ n ] - 1 + ( n - 2 ) ) ; } } prime_number . fill ( 0 ) ; var arr = [ 5 , 4 , 3 , 2 , 1 ] ; var N = arr . length ; min_steps ( arr , N ) ;