Maximize sum of count of distinct prime factors of K array elements | C ++ program for 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 ; Driver code ; Given array ; Size of the array ; Given value of K
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000000 NEW_LINE int maxSumOfDistinctPrimeFactors ( int arr [ ] , int N , int K ) { int CountDistinct [ MAX + 1 ] ; bool prime [ MAX + 1 ] ; for ( int i = 0 ; i <= MAX ; i ++ ) { CountDistinct [ i ] = 0 ; prime [ i ] = true ; } for ( long long int i = 2 ; i <= MAX ; i ++ ) { if ( prime [ i ] == true ) { CountDistinct [ i ] = 1 ; for ( long long int j = i * 2 ; j <= MAX ; j += i ) { CountDistinct [ j ] ++ ; prime [ j ] = false ; } } } int sum = 0 ; int PrimeFactor [ 20 ] = { 0 } ; for ( int i = 0 ; i < N ; i ++ ) { PrimeFactor [ CountDistinct [ arr [ i ] ] ] ++ ; } for ( int i = 19 ; i >= 1 ; i -- ) { while ( PrimeFactor [ i ] > 0 ) { sum += i ; PrimeFactor [ i ] -- ; K -- ; if ( K == 0 ) break ; } if ( K == 0 ) break ; } cout << sum ; } int main ( ) { int arr [ ] = { 6 , 9 , 12 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 2 ; maxSumOfDistinctPrimeFactors ( arr , N , K ) ; return 0 ; }