Count of subsets whose product is multiple of unique primes | Python program for the above approach ; Function to check number has distinct prime ; While N has factors of two ; Traversing till sqrt ( N ) ; If N has a factor of i ; While N has a factor of i ; Covering case , N is Prime ; Function to check wheather num can be added to the subset ; Recursive Function to count subset ; Base Case ; If currSubset is empty ; If Unique [ pos ] can be added to the Subset ; Function to count the subsets ; Initialize unique ; Check it is a product of distinct primes ; Count frequency of unique element ; Function Call ; Driver Code ; Given Input ; Function Call
from math import gcd , sqrt NEW_LINE def checkDistinctPrime ( n ) : NEW_LINE INDENT original = n NEW_LINE product = 1 NEW_LINE if ( n % 2 == 0 ) : NEW_LINE INDENT product *= 2 NEW_LINE while ( n % 2 == 0 ) : NEW_LINE INDENT n = n // 2 NEW_LINE DEDENT DEDENT for i in range ( 3 , int ( sqrt ( n ) ) , 2 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT product = product * i NEW_LINE while ( n % i == 0 ) : NEW_LINE INDENT n = n // i NEW_LINE DEDENT DEDENT DEDENT if ( n > 2 ) : NEW_LINE INDENT product = product * n NEW_LINE DEDENT return product == original NEW_LINE DEDENT def check ( pos , subset , unique ) : NEW_LINE INDENT for num in subset : NEW_LINE INDENT if gcd ( num , unique [ pos ] ) != 1 : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def countPrime ( pos , currSubset , unique , frequency ) : NEW_LINE INDENT if pos == len ( unique ) : NEW_LINE INDENT if not currSubset : NEW_LINE INDENT return 0 NEW_LINE DEDENT count = 1 NEW_LINE for element in currSubset : NEW_LINE INDENT count *= frequency [ element ] NEW_LINE DEDENT return count NEW_LINE DEDENT if check ( pos , currSubset , unique ) : NEW_LINE INDENT return countPrime ( pos + 1 , currSubset ,   \ unique , frequency ) + countPrime ( pos + 1 , currSubset + [ unique [ pos ] ] ,   \ unique , frequency ) NEW_LINE DEDENT else : NEW_LINE INDENT return countPrime ( pos + 1 , currSubset ,   \ unique , frequency ) NEW_LINE DEDENT DEDENT def countSubsets ( arr , N ) : NEW_LINE INDENT unique = set ( ) NEW_LINE for element in arr : NEW_LINE INDENT if checkDistinctPrime ( element ) : NEW_LINE INDENT unique . add ( element ) NEW_LINE DEDENT DEDENT unique = list ( unique ) NEW_LINE frequency = dict ( ) NEW_LINE for element in unique : NEW_LINE INDENT frequency [ element ] = arr . count ( element ) NEW_LINE DEDENT ans = countPrime ( 0 , [ ] , unique , frequency ) NEW_LINE return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 4 , 7 , 10 ] NEW_LINE N = len ( arr ) NEW_LINE ans = countSubsets ( arr , N ) NEW_LINE print ( ans ) NEW_LINE DEDENT