Maximize sum of count of distinct prime factors of K array elements | Python 3 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
MAX = 1000000 NEW_LINE def maxSumOfDistinctPrimeFactors ( arr , N , K ) : NEW_LINE INDENT CountDistinct = [ 0 ] * ( MAX + 1 ) NEW_LINE prime = [ False ] * ( MAX + 1 ) NEW_LINE for i in range ( MAX + 1 ) : NEW_LINE INDENT CountDistinct [ i ] = 0 NEW_LINE prime [ i ] = True NEW_LINE DEDENT for i in range ( 2 , MAX + 1 ) : NEW_LINE INDENT if ( prime [ i ] == True ) : NEW_LINE INDENT CountDistinct [ i ] = 1 NEW_LINE for j in range ( i * 2 , MAX + 1 , i ) : NEW_LINE INDENT CountDistinct [ j ] += 1 NEW_LINE prime [ j ] = False NEW_LINE DEDENT DEDENT DEDENT sum = 0 NEW_LINE PrimeFactor = [ 0 ] * 20 NEW_LINE for i in range ( N ) : NEW_LINE INDENT PrimeFactor [ CountDistinct [ arr [ i ] ] ] += 1 NEW_LINE DEDENT for i in range ( 19 , 0 , - 1 ) : NEW_LINE INDENT while ( PrimeFactor [ i ] > 0 ) : NEW_LINE INDENT sum += i NEW_LINE PrimeFactor [ i ] -= 1 NEW_LINE K -= 1 NEW_LINE if ( K == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( K == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT print ( sum ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 6 , 9 , 12 ] NEW_LINE N = len ( arr ) NEW_LINE K = 2 NEW_LINE maxSumOfDistinctPrimeFactors ( arr , N , K ) NEW_LINE DEDENT