Minimum replacement of pairs by their LCM required to reduce given array to its LCM | Python3 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 ; Given array arr ; Function call
maxm = 10001 ; NEW_LINE prime = [ True ] * ( maxm + 1 ) ; NEW_LINE prime_number = [ 0 ] * ( maxm + 1 ) ; NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT for p in range ( 2 , ( int ( maxm ** 1 / 2 ) ) ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , maxm , p ) : NEW_LINE INDENT prime [ i ] = False ; NEW_LINE DEDENT DEDENT DEDENT prime [ 0 ] = False ; NEW_LINE prime [ 1 ] = False ; NEW_LINE DEDENT def num_prime ( ) : NEW_LINE INDENT prime_number [ 0 ] = 0 ; NEW_LINE for i in range ( 1 , maxm + 1 ) : NEW_LINE INDENT tmp = - 1 ; NEW_LINE if ( prime [ i ] == True ) : NEW_LINE INDENT tmp = 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT tmp = 0 ; NEW_LINE DEDENT prime_number [ i ] = prime_number [ i - 1 ] + tmp ; NEW_LINE DEDENT DEDENT def min_steps ( arr , n ) : NEW_LINE INDENT SieveOfEratosthenes ( ) ; NEW_LINE num_prime ( ) ; NEW_LINE if ( n == 1 ) : NEW_LINE INDENT print ( "0" ) ; NEW_LINE DEDENT elif ( n == 2 ) : NEW_LINE INDENT print ( "1" ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( prime_number [ n ] - 1 + ( n - 2 ) ) ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 5 , 4 , 3 , 2 , 1 ] ; NEW_LINE N = len ( arr ) ; NEW_LINE min_steps ( arr , N ) ; NEW_LINE DEDENT