Minimum replacement of pairs by their LCM required to reduce given array to its LCM | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int maxm = 10001 ; bool prime [ maxm ] ; int prime_number [ maxm ] ; void SieveOfEratosthenes ( ) { memset ( prime , true , sizeof ( prime ) ) ; 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 ; } void num_prime ( ) { prime_number [ 0 ] = 0 ; for ( int i = 1 ; i <= maxm ; i ++ ) prime_number [ i ] = prime_number [ i - 1 ] + prime [ i ] ; } void min_steps ( int arr [ ] , int n ) { SieveOfEratosthenes ( ) ; num_prime ( ) ; if ( n == 1 ) cout << "0 STRNEWLINE " ; else if ( n == 2 ) cout << "1 STRNEWLINE " ; else cout << prime_number [ n ] - 1 + ( n - 2 ) ; } int main ( ) { int arr [ ] = { 5 , 4 , 3 , 2 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; min_steps ( arr , N ) ; return 0 ; }