Count of subsequences of length atmost K containing distinct prime elements | Python3 Program to find the count of distinct prime subsequences at most of of length K from a given array ; Initialize all indices as true ; A value in prime [ i ] will finally be false if i is not a prime , else true ; If prime [ p ] is true , then it is a prime ; Update all multiples of p as false , i . e . non - prime ; Returns number of subsequences of maximum length k and contains distinct primes ; Store the primes in the given array ; Sort the primes ; Store the frequencies of all the distinct primes ; Store the frequency of primes ; Store the sum of all frequencies ; Store the length of subsequence at every instant ; Store the frequency ; Store the previous count of updated DP ; Calculate total subsequences of current of_length ; Add the number of subsequences to the answer ; Update the value in dp [ i ] ; Store the updated dp [ i ] ; Driver Code
prime = [ True ] * 1000000 NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT global prime NEW_LINE prime [ 0 ] = prime [ 1 ] = False NEW_LINE p = 2 NEW_LINE while p * p <= 100000 : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , 100001 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def distinctPrimeSubSeq ( a , n , k ) : NEW_LINE INDENT SieveOfEratosthenes ( ) NEW_LINE primes = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( prime [ a [ i ] ] ) : NEW_LINE INDENT primes . append ( a [ i ] ) NEW_LINE DEDENT DEDENT l = len ( primes ) NEW_LINE primes . sort ( ) NEW_LINE b = [ ] NEW_LINE dp = [ ] NEW_LINE sum = 0 NEW_LINE i = 0 NEW_LINE while i < l : NEW_LINE INDENT count = 1 NEW_LINE x = a [ i ] NEW_LINE i += 1 NEW_LINE while ( i < l and a [ i ] == x ) : NEW_LINE INDENT count += 1 NEW_LINE i += 1 NEW_LINE DEDENT b . append ( count ) NEW_LINE dp . append ( count ) NEW_LINE sum += count NEW_LINE DEDENT of_length = 2 NEW_LINE leng = len ( dp ) NEW_LINE ans = 0 NEW_LINE while ( of_length <= k ) : NEW_LINE INDENT freq = 0 NEW_LINE prev = 0 NEW_LINE for i in range ( leng - 1 ) : NEW_LINE INDENT freq += dp [ i ] NEW_LINE j = sum - freq NEW_LINE subseq = b [ i ] * j NEW_LINE ans += subseq NEW_LINE dp [ i ] = subseq NEW_LINE prev += dp [ i ] NEW_LINE DEDENT leng -= 1 NEW_LINE sum = prev NEW_LINE of_length += 1 NEW_LINE DEDENT ans += ( l + 1 ) NEW_LINE return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 2 , 2 , 3 , 3 , 4 , 5 ] NEW_LINE n = len ( a ) NEW_LINE k = 3 NEW_LINE print ( distinctPrimeSubSeq ( a , n , k ) ) NEW_LINE DEDENT