Count of subsequences of length atmost K containing distinct prime elements | C # 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
using System ; using System . Collections . Generic ; class GFG { static bool [ ] prime = new bool [ 100001 ] ; static void SieveOfEratosthenes ( ) { for ( int i = 0 ; i < prime . Length ; i ++ ) prime [ i ] = true ; prime [ 0 ] = prime [ 1 ] = false ; for ( int p = 2 ; p * p < 100000 ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= 100000 ; i += p ) prime [ i ] = false ; } } } static int distinctPrimeSubSeq ( int [ ] a , int n , int k ) { SieveOfEratosthenes ( ) ; List < int > primes = new List < int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( prime [ a [ i ] ] ) primes . Add ( a [ i ] ) ; } int l = primes . Count ; primes . Sort ( ) ; List < int > b = new List < int > ( ) ; List < int > dp = new List < int > ( ) ; int sum = 0 ; for ( int i = 0 ; i < l ; ) { int count = 1 , x = a [ i ] ; i ++ ; while ( i < l && a [ i ] == x ) { count ++ ; i ++ ; } b . Add ( count ) ; dp . Add ( count ) ; sum += count ; } int of_length = 2 ; int len = dp . Count ; int ans = 0 ; while ( of_length <= k ) { int freq = 0 ; int prev = 0 ; for ( int i = 0 ; i < ( len ) ; i ++ ) { freq += dp [ i ] ; int j = sum - freq ; int subseq = b [ i ] * j ; ans += subseq ; dp [ i ] = subseq ; prev += dp [ i ] ; } len -- ; sum = prev ; of_length ++ ; } ans += ( l + 1 ) ; return ans ; } public static void Main ( String [ ] args ) { int [ ] a = { 1 , 2 , 2 , 3 , 3 , 4 , 5 } ; int n = a . Length ; int k = 3 ; Console . Write ( distinctPrimeSubSeq ( a , n , k ) ) ; } }