Minimize swaps required to make all prime | Python 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 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 ; Driver Code ; Pre - calculate prime [ ]
import math NEW_LINE mxn = 10000 + 1 NEW_LINE prime = [ True for _ in range ( mxn + 1 ) ] NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT global prime NEW_LINE for p in range ( 2 , int ( math . sqrt ( mxn ) ) + 1 ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , mxn + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT def countMin ( arr , n ) : NEW_LINE INDENT cMinSwaps = 0 NEW_LINE cPrimeIndices = 0 NEW_LINE cPrimeNos = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT if ( prime [ i + 1 ] ) : NEW_LINE INDENT cPrimeIndices += 1 NEW_LINE if ( not prime [ arr [ i ] ] ) : NEW_LINE INDENT cMinSwaps += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cPrimeNos += 1 NEW_LINE DEDENT DEDENT elif ( prime [ arr [ i ] ] ) : NEW_LINE INDENT cPrimeNos += 1 NEW_LINE DEDENT DEDENT if ( cPrimeNos >= cPrimeIndices ) : NEW_LINE INDENT return cMinSwaps NEW_LINE DEDENT else : NEW_LINE INDENT return - 1 NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT SieveOfEratosthenes ( ) NEW_LINE n = 5 NEW_LINE arr = [ 2 , 7 , 8 , 5 , 13 ] NEW_LINE print ( countMin ( arr , n ) ) NEW_LINE DEDENT