Minimum changes required to make all Array elements Prime | Java 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
import java . util . * ; import java . lang . * ; class GFG { static ArrayList < Integer > SieveOfEratosthenes ( int n ) { boolean [ ] prime = new boolean [ 2 * n + 1 ] ; Arrays . 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 ; } } ArrayList < Integer > primes = new ArrayList < > ( ) ; 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 ] ) ; ArrayList < Integer > primes = SieveOfEratosthenes ( maxi ) ; for ( int i = 0 ; i < n ; i ++ ) { int x = - 1 ; for ( int j = 0 ; j < primes . size ( ) ; j ++ ) { if ( arr [ i ] == primes . get ( j ) ) { x = j ; break ; } else if ( arr [ i ] < primes . get ( j ) ) { x = j ; break ; } } int minm = Math . abs ( primes . get ( x ) - arr [ i ] ) ; if ( x > 1 ) { minm = Math . min ( minm , Math . abs ( primes . get ( x - 1 ) - arr [ i ] ) ) ; } ans += minm ; } return ans ; } public static void main ( String [ ] args ) { int [ ] arr = { 4 , 25 , 13 , 6 , 20 } ; System . out . println ( minChanges ( arr ) ) ; } }