Minimize sum of K positive integers with given LCM | Function to find the prime power of X ; Stores prime powers of X ; Iterate over the range [ 2 , sqrt ( X ) ] ; If X is divisible by i ; Stores prime power ; Calculate prime power of X ; Update X ; Update p ; Insert prime powers into primePow [ ] ; If X exceeds 1 ; Function to calculate the sum of array elements ; Stores sum of array elements ; Traverse the array ; Update sum ; Function to partition array into K groups such that sum of elements of the K groups is minimum ; If count of prime powers is equal to pos ; Stores minimum sum of of each partition of arr [ ] into K groups ; Traverse the array arr [ ] ; Include primePow [ pos ] into i - th groups ; Update res ; Remove factors [ pos ] from i - th groups ; Utility function to calculate minimum sum of K positive integers whose LCM is X ; Stores all prime powers of X ; Stores count of prime powers ; Stores minimum sum of K positive integers whose LCM is X ; If n is less than or equal to k ; Traverse primePow [ ] array ; Update sum ; Update sum ; arr [ i ] : Stores element in i - th group by partitioning the primePow [ ] array ; Update sum ; Driver Code
def primePower ( X ) : NEW_LINE INDENT primePow = [ ] NEW_LINE for i in range ( 2 , X + 1 ) : NEW_LINE INDENT if i * i > X + 1 : NEW_LINE INDENT break NEW_LINE DEDENT if ( X % i == 0 ) : NEW_LINE INDENT p = 1 NEW_LINE while ( X % i == 0 ) : NEW_LINE INDENT X //= i NEW_LINE p *= i NEW_LINE DEDENT primePow . append ( p ) NEW_LINE DEDENT DEDENT if ( X > 1 ) : NEW_LINE INDENT primePow . append ( X ) NEW_LINE DEDENT return primePow NEW_LINE DEDENT def getSum ( ar ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in ar : NEW_LINE INDENT sum += i NEW_LINE DEDENT return sum NEW_LINE DEDENT def getMinSum ( pos , arr , primePow ) : NEW_LINE INDENT if ( pos == len ( primePow ) ) : NEW_LINE INDENT return getSum ( arr ) NEW_LINE DEDENT res = 10 ** 9 NEW_LINE for i in range ( len ( arr ) ) : NEW_LINE INDENT arr [ i ] *= primePow [ pos ] NEW_LINE res = min ( res , getMinSum ( pos + 1 , arr , primePow ) ) NEW_LINE arr [ i ] //= primePow [ pos ] NEW_LINE DEDENT return res NEW_LINE DEDENT def minimumSumWithGivenLCM ( k , x ) : NEW_LINE INDENT primePow = primePower ( x ) NEW_LINE n = len ( primePow ) NEW_LINE sum = 0 NEW_LINE if ( n <= k ) : NEW_LINE INDENT for i in primePow : NEW_LINE INDENT sum += i NEW_LINE DEDENT sum += k - n NEW_LINE DEDENT else : NEW_LINE INDENT arr = [ 1 ] * ( k ) NEW_LINE sum = getMinSum ( 0 , arr , primePow ) NEW_LINE DEDENT return sum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT k = 3 NEW_LINE x = 210 NEW_LINE print ( minimumSumWithGivenLCM ( k , x ) ) NEW_LINE DEDENT