Minimum number of operations required to make all elements of at least one row of given Matrix prime | Python 3 program to implement the above approach ; Function to generate all prime numbers using Sieve of Eratosthenes ; Function to check if a number is prime or not ; prime [ i ] : Check if i is a prime number or not ; Iterate over the range [ 2 , sqrt ( n ) ] ; If p is a prime number ; Mark all multiples of i to false ; Update i ; Function to find minimum operations to make all elements of at least one row of the matrix as prime numbers ; dp [ i ] : Stores minimum operations to get i prime numbers in a row ; Traverse the array ; Stores count of prime numbers in a i - th row ; Iterate over the range [ ( 1 << m ) - 1 , 0 ] ; If a row exist which contains j prime numbers ; Update dp [ j bitmask ] ; Update dp [ bitmask ] ; Return minimum operations to get a row of the matrix with all prime numbers ; Function to count prime numbers in a row ; i - th bit of bitmask check if i - th column is a prime or not ; Traverse the array ; if a [ i ] is a prime number ; Update bitmask ; Driver Code ; Stores count of columns in the matrix ; Stores length ; Calculate all prime numbers in range [ 1 , max ] using sieve ; Function Call
from math import sqrt NEW_LINE prime = [ True for i in range ( 10001 ) ] NEW_LINE def sieve ( n ) : NEW_LINE INDENT global prime NEW_LINE for p in range ( 2 , int ( sqrt ( 10000 ) ) + 1 , 1 ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , 10001 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT def MinWays ( a , n , m ) : NEW_LINE INDENT dp = [ n + 1 for i in range ( 1 << m ) ] NEW_LINE for i in range ( len ( a ) ) : NEW_LINE INDENT bitmask = BitMask ( a [ i ] ) NEW_LINE j = ( 1 << m ) - 1 NEW_LINE while ( j >= 0 ) : NEW_LINE INDENT if ( dp [ j ] != n + 1 ) : NEW_LINE INDENT dp [ j bitmask ] = min ( dp [ j bitmask ] , dp [ j ] + 1 ) NEW_LINE DEDENT j -= 1 NEW_LINE DEDENT dp [ bitmask ] = 1 NEW_LINE DEDENT if ( dp [ ( 1 << m ) - 1 ] - 1 ) == ( n + 1 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return ( dp [ ( 1 << m ) - 1 ] - 1 ) NEW_LINE DEDENT DEDENT def BitMask ( a ) : NEW_LINE INDENT global prime NEW_LINE bitmask = 0 NEW_LINE for i in range ( len ( a ) ) : NEW_LINE INDENT if ( prime [ a [ i ] ] ) : NEW_LINE INDENT bitmask |= ( 1 << i ) NEW_LINE DEDENT DEDENT return bitmask NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 4 , 6 , 5 , 8 ] , [ 2 , 9 , 12 , 14 ] , [ 32 , 7 , 18 , 16 ] , [ 12 , 4 , 35 , 17 ] ] NEW_LINE m = len ( mat [ 0 ] ) NEW_LINE n = len ( mat ) NEW_LINE max = 10000 NEW_LINE sieve ( max ) NEW_LINE print ( MinWays ( mat , n , m ) ) NEW_LINE DEDENT