Minimize swaps required to make all prime | Function to pre - calculate the prime [ ] prime [ i ] denotes whether i is prime or not ; 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 greater than or equal to the square of it numbers which are multiple of p and are less than p ^ 2 are already been marked . ; 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 ; Pre - calculate prime [ ]
const mxn = 1e4 + 1 ; let prime = new Array ( mxn + 1 ) ; function SieveOfEratosthenes ( ) { prime . fill ( true ) ; for ( let p = 2 ; p * p <= mxn ; p ++ ) { if ( prime [ p ] == true ) { for ( let i = p * p ; i <= mxn ; i += p ) prime [ i ] = false ; } } } function countMin ( arr , n ) { let cMinSwaps = 0 ; let cPrimeIndices = 0 ; let cPrimeNos = 0 ; for ( let i = 0 ; i < n ; i ++ ) { if ( prime [ i + 1 ] ) { cPrimeIndices ++ ; if ( ! prime [ arr [ i ] ] ) cMinSwaps ++ ; else cPrimeNos ++ ; } else if ( prime [ arr [ i ] ] ) { cPrimeNos ++ ; } } if ( cPrimeNos >= cPrimeIndices ) return cMinSwaps ; else return - 1 ; } SieveOfEratosthenes ( ) ; let n = 5 ; let arr = [ 2 , 7 , 8 , 5 , 13 ] ; document . write ( countMin ( arr , n ) ) ;