Minimize swaps required to make all prime | Java program for the above approach ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries it as true . A value in prime [ i ] will finally be false if i is Not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Function to count minimum number of swaps required ; To count the minimum number of swaps required to convert the array into perfectly prime ; To count total number of prime indexes in the array ; To count the total number of prime numbers in the array ; Check whether index is prime or not ; Element is not prime ; If the total number of prime numbers is greater than or equal to the total number of prime indices , then it is possible to convert the array into perfectly prime ; Driver Code ; Pre - calculate prime [ ]
import java . io . * ; class GFG { static boolean prime [ ] = new boolean [ ( int ) 1e4 + 2 ] ; static void SieveOfEratosthenes ( ) { for ( int i = 0 ; i < ( int ) 1e4 + 2 ; i ++ ) prime [ i ] = true ; for ( int p = 2 ; p * p < ( int ) 1e4 + 2 ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i < ( int ) 1e4 + 2 ; i += p ) prime [ i ] = false ; } } } static int countMin ( int [ ] arr , int n ) { int cMinSwaps = 0 ; int cPrimeIndices = 0 ; int cPrimeNos = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( prime [ i + 1 ] ) { cPrimeIndices ++ ; if ( prime [ arr [ i ] ] == false ) cMinSwaps ++ ; else cPrimeNos ++ ; } else if ( prime [ arr [ i ] ] ) { cPrimeNos ++ ; } } if ( cPrimeNos >= cPrimeIndices ) return cMinSwaps ; else return - 1 ; } public static void main ( String [ ] args ) { SieveOfEratosthenes ( ) ; int n = 5 ; int arr [ ] = { 2 , 7 , 8 , 5 , 13 } ; System . out . println ( countMin ( arr , n ) ) ; } }