Find the length of the Largest subset such that all elements are Pairwise Coprime | C # implementation to find the length of the largest subset such that all elements are Pairwise Coprime ; Dynamic programming table ; Function to obtain the mask for any integer ; List of prime numbers till 50 ; Iterate through all prime numbers to obtain the mask ; Set this prime 's bit ON in the mask ; Return the mask value ; Function to count the number of ways ; Check if subproblem has been solved ; Excluding current element in the subset ; Check if there are no common prime factors then only this element can be included ; Calculate the new mask if this element is included ; Store and return the answer ; Function to find the count of subarray with all digits unique ; Driver code
using System ; class GFG { static int [ , ] dp = new int [ 5000 , 1029 ] ; static int getmask ( int val ) { int mask = 0 ; int [ ] prime = { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 } ; for ( int i = 0 ; i < 15 ; i ++ ) { if ( val % prime [ i ] == 0 ) { mask = mask | ( 1 << i ) ; } } return mask ; } static int calculate ( int pos , int mask , int [ ] a , int n ) { if ( pos == n || mask == ( int ) ( 1 << n - 1 ) ) return 0 ; if ( dp [ pos , mask ] != - 1 ) return dp [ pos , mask ] ; int size = 0 ; size = Math . Max ( size , calculate ( pos + 1 , mask , a , n ) ) ; if ( ( getmask ( a [ pos ] ) & mask ) == 0 ) { int new_mask = ( mask | ( getmask ( a [ pos ] ) ) ) ; size = Math . Max ( size , 1 + calculate ( pos + 1 , new_mask , a , n ) ) ; } return dp [ pos , mask ] = size ; } static int largestSubset ( int [ ] a , int n ) { for ( int i = 0 ; i < 5000 ; i ++ ) { for ( int j = 0 ; j < 1029 ; j ++ ) dp [ i , j ] = - 1 ; } return calculate ( 0 , 0 , a , n ) ; } public static void Main ( ) { int [ ] A = { 2 , 3 , 13 , 5 , 14 , 6 , 7 , 11 } ; int N = A . Length ; Console . WriteLine ( largestSubset ( A , N ) ) ; } }