Maximize sum of count of distinct prime factors of K array elements | Java 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
import java . io . * ; class GFG { public static int MAX = 1000000 ; static void maxSumOfDistinctPrimeFactors ( int [ ] arr , int N , int K ) { int [ ] CountDistinct = new int [ MAX + 1 ] ; boolean [ ] prime = new boolean [ MAX + 1 ] ; for ( int i = 0 ; i <= MAX ; i ++ ) { CountDistinct [ i ] = 0 ; prime [ i ] = true ; } for ( int i = 2 ; i <= MAX ; i ++ ) { if ( prime [ i ] == true ) { CountDistinct [ i ] = 1 ; for ( int j = i * 2 ; j <= MAX ; j += i ) { CountDistinct [ j ] ++ ; prime [ j ] = false ; } } } int sum = 0 ; int [ ] PrimeFactor = new int [ 20 ] ; 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 ; } System . out . print ( sum ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 6 , 9 , 12 } ; int N = arr . length ; int K = 2 ; maxSumOfDistinctPrimeFactors ( arr , N , K ) ; } }