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 ; Initializing dp ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 5000 ] [ ( 1 << 10 ) + 5 ] ; int getmask ( int val ) { int mask = 0 ; int prime [ 15 ] = { 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 ; } int calculate ( int pos , int mask , int a [ ] , int n ) { if ( pos == n || mask == ( 1 << n - 1 ) ) return 0 ; if ( dp [ pos ] [ mask ] != -1 ) return dp [ pos ] [ mask ] ; int size = 0 ; size = max ( size , calculate ( pos + 1 , mask , a , n ) ) ; if ( ( getmask ( a [ pos ] ) & mask ) == 0 ) { int new_mask = ( mask | ( getmask ( a [ pos ] ) ) ) ; size = max ( size , 1 + calculate ( pos + 1 , new_mask , a , n ) ) ; } return dp [ pos ] [ mask ] = size ; } int largestSubset ( int a [ ] , int n ) { memset ( dp , -1 , sizeof ( dp ) ) ; return calculate ( 0 , 0 , a , n ) ; } int main ( ) { int A [ ] = { 2 , 3 , 13 , 5 , 14 , 6 , 7 , 11 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << largestSubset ( A , N ) ; return 0 ; }