Minimum replacement of pairs by their LCM required to reduce given array to its LCM | Java 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 ; Driver code ; Stores the prefix sum of the count of prime numbers ; Given array arr [ ] ; Function call
import java . util . * ; class GFG { static final int maxm = 10001 ; static boolean prime [ ] ; static int prime_number [ ] ; static void SieveOfEratosthenes ( ) { Arrays . fill ( prime , true ) ; for ( int p = 2 ; p * p < maxm ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i < maxm ; i += p ) prime [ i ] = false ; } } prime [ 0 ] = false ; prime [ 1 ] = false ; } static void num_prime ( ) { prime_number [ 0 ] = 0 ; for ( int i = 1 ; i <= maxm ; i ++ ) { int tmp ; if ( prime [ i ] == true ) { tmp = 1 ; } else { tmp = 0 ; } prime_number [ i ] = prime_number [ i - 1 ] + tmp ; } } static void min_steps ( int arr [ ] , int n ) { SieveOfEratosthenes ( ) ; num_prime ( ) ; if ( n == 1 ) { System . out . println ( "0" ) ; } else if ( n == 2 ) { System . out . println ( "1" ) ; } else { System . out . println ( prime_number [ n ] - 1 + ( n - 2 ) ) ; } } public static void main ( String [ ] args ) { prime = new boolean [ maxm + 1 ] ; prime_number = new int [ maxm + 1 ] ; int arr [ ] = { 5 , 4 , 3 , 2 , 1 } ; int N = arr . length ; min_steps ( arr , N ) ; } }