Minimize sum of prime numbers added to make an array non | Javascript 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 ; Given array ; Function Call
let MAX = 10000000 ; let isPrime = new Array ( MAX ) ; let primes = new Array ( ) ; function SieveOfEratosthenes ( ) { isPrime . fill ( true ) ; for ( let p = 2 ; p * p <= MAX ; p ++ ) { if ( isPrime [ p ] == true ) { for ( let i = p * p ; i <= MAX ; i += p ) isPrime [ i ] = false ; } } for ( let p = 2 ; p <= MAX ; p ++ ) if ( isPrime [ p ] ) primes . push ( p ) ; } function prime_search ( primes , diff ) { let low = 0 ; let high = primes . length - 1 ; let res = 0 ; while ( low <= high ) { let mid = Math . floor ( ( 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 ; } function minCost ( arr , n ) { SieveOfEratosthenes ( ) ; let res = 0 ; for ( let i = 1 ; i < n ; i ++ ) { if ( arr [ i ] < arr [ i - 1 ] ) { let diff = arr [ i - 1 ] - arr [ i ] ; let closest_prime = prime_search ( primes , diff ) ; res += closest_prime ; arr [ i ] += closest_prime ; } } return res ; } let arr = [ 2 , 1 , 5 , 4 , 3 ] ; let n = 5 ; document . write ( minCost ( arr , n ) )