Minimum changes required to make all Array elements Prime | C # program to implement the above approach ; 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
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { static List < int > SieveOfEratosthenes ( int n ) { bool [ ] prime = new bool [ 2 * n + 1 ] ; Array . Fill ( prime , true ) ; for ( int p = 2 ; p * p <= 2 * n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= 2 * n ; i += p ) prime [ i ] = false ; } } List < int > primes = new List < int > ( ) ; for ( int p = 2 ; p <= 2 * n ; p ++ ) if ( prime [ p ] ) primes . Add ( p ) ; return primes ; } static int minChanges ( int [ ] arr ) { int n = arr . Length ; int ans = 0 ; int maxi = arr [ 0 ] ; for ( int i = 1 ; i < arr . Length ; i ++ ) maxi = Math . Max ( maxi , arr [ i ] ) ; List < int > primes = SieveOfEratosthenes ( maxi ) ; for ( int i = 0 ; i < n ; i ++ ) { int x = - 1 ; for ( int j = 0 ; j < primes . Count ; j ++ ) { if ( arr [ i ] == primes [ j ] ) { x = j ; break ; } else if ( arr [ i ] < primes [ j ] ) { x = j ; break ; } } int 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 ; } public static void Main ( string [ ] args ) { int [ ] arr = { 4 , 25 , 13 , 6 , 20 } ; Console . Write ( minChanges ( arr ) ) ; } }