Find the length of the Largest subset such that all elements are Pairwise Coprime | Java 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
import java . util . * ; 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 ++ ) Arrays . fill ( dp [ i ] , - 1 ) ; return calculate ( 0 , 0 , a , n ) ; } public static void main ( String args [ ] ) { int A [ ] = { 2 , 3 , 13 , 5 , 14 , 6 , 7 , 11 } ; int N = A . length ; System . out . println ( largestSubset ( A , N ) ) ; } }