Count of subsequences of length atmost K containing distinct prime elements | Javascript 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
let prime = new Array ( 100001 ) ; function SieveOfEratosthenes ( ) { prime . fill ( true ) prime [ 0 ] = prime [ 1 ] = false ; for ( let p = 2 ; p * p <= 100000 ; p ++ ) { if ( prime [ p ] == true ) { for ( let i = p * p ; i <= 100000 ; i += p ) prime [ i ] = false ; } } } function distinctPrimeSubSeq ( a , n , k ) { SieveOfEratosthenes ( ) ; let primes = new Array ( ) ; for ( let i = 0 ; i < n ; i ++ ) { if ( prime [ a [ i ] ] ) primes . push ( a [ i ] ) ; } let l = primes . length ; primes . sort ( ( a , b ) => a - b ) let b = new Array ( ) ; let dp = new Array ( ) ; let sum = 0 ; for ( let i = 0 ; i < l ; ) { let count = 1 , x = a [ i ] ; i ++ ; while ( i < l && a [ i ] == x ) { count ++ ; i ++ ; } b . push ( count ) ; dp . push ( count ) ; sum += count ; } let of_length = 2 ; let len = dp . length ; let ans = 0 ; while ( of_length <= k ) { let freq = 0 ; let prev = 0 ; for ( let i = 0 ; i < ( len - 1 ) ; i ++ ) { freq += dp [ i ] ; let j = sum - freq ; let subseq = b [ i ] * j ; ans += subseq ; dp [ i ] = subseq ; prev += dp [ i ] ; } len -- ; sum = prev ; of_length ++ ; } ans += ( l + 1 ) ; return ans ; } let a = [ 1 , 2 , 2 , 3 , 3 , 4 , 5 ] ; let n = a . length ; let k = 3 ; document . write ( distinctPrimeSubSeq ( a , n , k ) ) ;