Minimize sum of K positive integers with given LCM | C # program to implement the above approach ; Function to find the prime power of X ; Stores prime powers of X ; Iterate over the range [ 2 , Math . 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
using System ; using System . Collections . Generic ; class GFG { static List < int > primePower ( int X ) { List < int > primePow = new List < int > ( ) ; for ( int i = 2 ; i * i <= X ; i ++ ) { if ( X % i == 0 ) { int p = 1 ; while ( X % i == 0 ) { X /= i ; p *= i ; } primePow . Add ( p ) ; } } if ( X > 1 ) { primePow . Add ( X ) ; } return primePow ; } static int getSum ( int [ ] ar ) { int sum = 0 ; foreach ( int i in ar ) { sum += i ; } return sum ; } static int getMinSum ( int pos , int [ ] arr , List < int > primePow ) { if ( pos == primePow . Count ) { return getSum ( arr ) ; } int res = int . MaxValue ; for ( int i = 0 ; i < arr . Length ; i ++ ) { arr [ i ] *= primePow [ pos ] ; res = Math . Min ( res , getMinSum ( pos + 1 , arr , primePow ) ) ; arr [ i ] /= primePow [ pos ] ; } return res ; } static int minimumSumWithGivenLCM ( int k , int x ) { List < int > primePow = primePower ( x ) ; int n = primePow . Count ; int sum = 0 ; if ( n <= k ) { foreach ( int i in primePow ) { sum += i ; } sum += k - n ; } else { int [ ] arr = new int [ k ] ; for ( int l = 0 ; l < arr . Length ; l ++ ) arr [ l ] = 1 ; sum = getMinSum ( 0 , arr , primePow ) ; } return sum ; } public static void Main ( String [ ] args ) { int k = 3 , x = 210 ; Console . Write ( minimumSumWithGivenLCM ( k , x ) ) ; } }