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
dp = [ [ - 1 ] * ( ( 1 << 10 ) + 5 ) ] * 5000 NEW_LINE def getmask ( val ) : NEW_LINE INDENT mask = 0 NEW_LINE prime = [ 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 ] NEW_LINE for i in range ( 1 , 15 ) : NEW_LINE INDENT if val % prime [ i ] == 0 : NEW_LINE INDENT mask = mask | ( 1 << i ) NEW_LINE DEDENT DEDENT return mask NEW_LINE DEDENT def calculate ( pos , mask , a , n ) : NEW_LINE INDENT if ( ( pos == n ) or ( mask == ( 1 << n - 1 ) ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if dp [ pos ] [ mask ] != - 1 : NEW_LINE INDENT return dp [ pos ] [ mask ] NEW_LINE DEDENT size = 0 NEW_LINE size = max ( size , calculate ( pos + 1 , mask , a , n ) ) NEW_LINE if ( getmask ( a [ pos ] ) & mask ) == 0 : NEW_LINE INDENT new_mask = ( mask | ( getmask ( a [ pos ] ) ) ) NEW_LINE size = max ( size , 1 + calculate ( pos + 1 , new_mask , a , n ) ) NEW_LINE DEDENT dp [ pos ] [ mask ] = size NEW_LINE return dp [ pos ] [ mask ] NEW_LINE DEDENT def largestSubset ( A , n ) : NEW_LINE INDENT return calculate ( 0 , 0 , A , n ) ; NEW_LINE DEDENT A = [ 2 , 3 , 13 , 5 , 14 , 6 , 7 , 11 ] NEW_LINE N = len ( A ) NEW_LINE print ( largestSubset ( A , N ) ) NEW_LINE