Maximize sum of count of distinct prime factors of K array elements | JavaScript program of the above approach ; Function to find the maximum sum of count of distinct prime factors of K array elements ; Stores the count of distinct primes ; Stores 1 and 0 at prime and non - prime indices respectively ; Initialize the count of factors to 0 ; Sieve of Eratosthenes ; Count of factors of a prime number is 1 ; Increment CountDistinct of all multiples of i ; Mark its multiples non - prime ; Stores the maximum sum of distinct prime factors of K array elements ; Stores the count of all distinct prime factors ; Traverse the array to find count of all array elements ; Maximum sum of K prime factors of array elements ; Check for the largest prime factor ; Increment sum ; Decrement its count and K ; Print the maximum sum ; Given array ; Size of the array ; Given value of K
let MAX = 1000000 ; function maxSumOfDistinctPrimeFactors ( arr , N , K ) { let CountDistinct = [ ] ; for ( let i = 0 ; i <= MAX ; i ++ ) { CountDistinct [ i ] = 0 ; } let prime = [ ] ; for ( let i = 0 ; i <= MAX ; i ++ ) { prime [ i ] = 0 ; } for ( let i = 0 ; i <= MAX ; i ++ ) { CountDistinct [ i ] = 0 ; prime [ i ] = true ; } for ( let i = 2 ; i <= MAX ; i ++ ) { if ( prime [ i ] == true ) { CountDistinct [ i ] = 1 ; for ( let j = i * 2 ; j <= MAX ; j += i ) { CountDistinct [ j ] ++ ; prime [ j ] = false ; } } } let sum = 0 ; let PrimeFactor = [ ] ; for ( let i = 0 ; i <= 20 ; i ++ ) { PrimeFactor [ i ] = 0 ; } for ( let i = 0 ; i < N ; i ++ ) { PrimeFactor [ CountDistinct [ arr [ i ] ] ] ++ ; } for ( let i = 19 ; i >= 1 ; i -- ) { while ( PrimeFactor [ i ] > 0 ) { sum += i ; PrimeFactor [ i ] -- ; K -- ; if ( K == 0 ) break ; } if ( K == 0 ) break ; } document . write ( sum ) ; } let arr = [ 6 , 9 , 12 ] ; let N = arr . length ; let K = 2 ; maxSumOfDistinctPrimeFactors ( arr , N , K ) ;