Minimum number of operations required to make all elements of at least one row of given Matrix prime | 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
let prime = [ ] ; function sieve ( n ) { prime = new Array ( n + 1 ) ; for ( let i = 0 ; i < prime . length ; i ++ ) prime [ i ] = true ; for ( let p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( let i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } } function MinWays ( a , n , m ) { let dp = new Array ( 1 << m ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = n + 1 ; } for ( let i = 0 ; i < a . length ; i ++ ) { let bitmask = BitMask ( a [ i ] ) ; for ( let 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 ) ; } function BitMask ( a ) { let bitmask = 0 ; for ( let i = 0 ; i < a . length ; i ++ ) { if ( prime [ a [ i ] ] ) { bitmask |= ( 1 << i ) ; } } return bitmask ; } let mat = [ [ 4 , 6 , 5 , 8 ] , [ 2 , 9 , 12 , 14 ] , [ 32 , 7 , 18 , 16 ] , [ 12 , 4 , 35 , 17 ] ] ; let m = mat [ 0 ] . length ; let n = mat . length ; let max = 10000 ; sieve ( max ) ; document . write ( MinWays ( mat , n , m ) ) ;