text: Minimize sum of prime numbers added to make an array non | C ++ Program to implement the above approach ; Stores if an index is a prime / non - prime value ; Stores the prime ; Function to generate all prime numbers ; If current element is prime ; Set all its multiples non - prime ; Store all prime numbers ; Function to find the closest prime to a particular number ; Applying binary search on primes vector ; If the prime added makes the elements equal ; Return this as the closest prime ; If the array remains non - decreasing ; Search for a bigger prime number ; Otherwise ; Check if a smaller prime can make array non - decreasing or not ; Return closest number ; Function to find the minimum cost ; Find all primes ; Store the result ; Iterate over the array ; Current element is less than the previous element ; Find the closest prime which makes the array non decreasing ; Add to overall cost ; Update current element ; Return the minimum cost ; Driver Code ; Given array ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  10000000 NEW_LINE bool isPrime [ MAX ] ; vector < int > primes ; void SieveOfEratosthenes ( ) { memset ( isPrime , true , sizeof ( isPrime ) ) ; for ( int p = 2 ; p * p <= MAX ; p ++ ) { if ( isPrime [ p ] == true ) { for ( int i = p * p ; i <= MAX ; i += p ) isPrime [ i ] = false ; } } for ( int p = 2 ; p <= MAX ; p ++ ) if ( isPrime [ p ] ) primes . push_back ( p ) ; } int prime_search ( vector < int > primes , int diff ) { int low = 0 ; int high = primes . size ( ) - 1 ; int res ; while ( low <= high ) { int mid = ( low + high ) / 2 ; if ( primes [ mid ] == diff ) { return primes [ mid ] ; } else if ( primes [ mid ] < diff ) { low = mid + 1 ; } else { res = primes [ mid ] ; high = mid - 1 ; } } return res ; } int minCost ( int arr [ ] , int n ) { SieveOfEratosthenes ( ) ; int res = 0 ; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] < arr [ i - 1 ] ) { int diff = arr [ i - 1 ] - arr [ i ] ; int closest_prime = prime_search ( primes , diff ) ; res += closest_prime ; arr [ i ] += closest_prime ; } } return res ; } int main ( ) { int arr [ ] = { 2 , 1 , 5 , 4 , 3 } ; int n = 5 ; cout << minCost ( arr , n ) ; return 0 ; }