Minimum number of operations required to make all elements of at least one row of given Matrix prime | C # 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 ; Initialize prime [ ] array to true ; 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 ; Initialize [ ] dp array to ( n + 1 ) ; 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
using System ; public class GFG { private static bool [ ] prime ; private static void sieve ( int n ) { prime = new bool [ n + 1 ] ; for ( int i = 0 ; i < prime . Length ; i ++ ) prime [ i ] = true ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } } private static int MinWays ( int [ , ] a , int n , int m ) { int [ ] dp = new int [ 1 << m ] ; for ( int i = 0 ; i < dp . Length ; i ++ ) { dp [ i ] = n + 1 ; } for ( int i = 0 ; i < a . GetLength ( 0 ) ; i ++ ) { int bitmask = BitMask ( GetRow ( a , i ) ) ; for ( int j = ( 1 << m ) - 1 ; j >= 0 ; j -- ) { if ( dp [ j ] != n + 1 ) { dp [ j bitmask ] = Math . Min ( dp [ j bitmask ] , dp [ j ] + 1 ) ; } } dp [ bitmask ] = 1 ; } return ( dp [ ( 1 << m ) - 1 ] - 1 ) == ( n + 1 ) ? - 1 : ( dp [ ( 1 << m ) - 1 ] - 1 ) ; } private static int BitMask ( int [ ] a ) { int bitmask = 0 ; for ( int i = 0 ; i < a . Length ; i ++ ) { if ( prime [ a [ i ] ] ) { bitmask |= ( 1 << i ) ; } } return bitmask ; } public static int [ ] GetRow ( int [ , ] matrix , int row ) { var rowLength = matrix . GetLength ( 1 ) ; var rowVector = new int [ rowLength ] ; for ( var i = 0 ; i < rowLength ; i ++ ) rowVector [ i ] = matrix [ row , i ] ; return rowVector ; } public static void Main ( String [ ] args ) { int [ , ] mat = { { 4 , 6 , 5 , 8 } , { 2 , 9 , 12 , 14 } , { 32 , 7 , 18 , 16 } , { 12 , 4 , 35 , 17 } } ; int m = mat . GetLength ( 0 ) ; int n = mat . GetLength ( 1 ) ; int max = 10000 ; sieve ( max ) ; Console . WriteLine ( MinWays ( mat , n , m ) ) ; } }