Minimize sum of prime numbers added to make an array non | Java 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
import java . util . * ; class GFG { static final int MAX = 10000000 ; static boolean [ ] isPrime = new boolean [ MAX + 1 ] ; static Vector < Integer > primes = new Vector < Integer > ( ) ; static void SieveOfEratosthenes ( ) { Arrays . fill ( isPrime , true ) ; 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 . add ( p ) ; } static int prime_search ( Vector < Integer > primes , int diff ) { int low = 0 ; int high = primes . size ( ) - 1 ; int res = - 1 ; while ( low <= high ) { int mid = ( low + high ) / 2 ; if ( primes . get ( mid ) == diff ) { return primes . get ( mid ) ; } else if ( primes . get ( mid ) < diff ) { low = mid + 1 ; } else { res = primes . get ( mid ) ; high = mid - 1 ; } } return res ; } static 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 ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 1 , 5 , 4 , 3 } ; int n = 5 ; System . out . print ( minCost ( arr , n ) ) ; } }