Minimum changes required to make all Array elements Prime | Function to generate all primes ; If p is a prime ; Mark all its multiples as non - prime ; Store all prime numbers ; Return the list of primes ; Function to calculate the minimum increments to convert every array elements to a prime ; Extract maximum element of the given array ; Extract the index which has the next greater prime ; Store the difference between the prime and the array element ; Driver Code
function SieveOfEratosthenes ( n ) { let prime = new Array ( 2 * n + 1 ) ; prime . fill ( true ) for ( let p = 2 ; p * p <= 2 * n ; p ++ ) { if ( prime [ p ] == true ) { for ( let i = p * p ; i <= 2 * n ; i += p ) prime [ i ] = false ; } } let primes = new Array ( ) ; for ( let p = 2 ; p <= 2 * n ; p ++ ) if ( prime [ p ] ) primes . push ( p ) ; return primes ; } function minChanges ( arr ) { let n = arr . length ; let ans = 0 ; let maxi = arr . sort ( ( a , b ) => b - a ) [ 0 ] ; let primes = SieveOfEratosthenes ( maxi ) ; for ( let i = 0 ; i < n ; i ++ ) { let x = - 1 for ( let j = 0 ; j < primes . length ; j ++ ) { if ( arr [ i ] == primes [ j ] ) { x = j break } else if ( arr [ i ] < primes [ j ] ) { x = j break } } let minm = Math . abs ( primes [ x ] - arr [ i ] ) ; if ( x > 1 ) { minm = Math . min ( minm , Math . abs ( primes [ x - 1 ] - arr [ i ] ) ) ; } ans += minm ; } return ans ; } let arr = [ 4 , 25 , 13 , 6 , 20 ] ; document . write ( minChanges ( arr ) ) ;