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 , 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
function primePower ( X ) { let primePow = [ ] ; for ( let i = 2 ; i * i <= X ; i ++ ) { if ( X % i == 0 ) { let p = 1 ; while ( X % i == 0 ) { X /= i ; p *= i ; } primePow . push ( p ) ; } } if ( X > 1 ) { primePow . push ( X ) ; } return primePow ; } function getSum ( ar ) { let sum = 0 ; for ( let i = 0 ; i < ar . length ; i ++ ) { sum += ar [ i ] ; } return sum ; } function getMinSum ( pos , arr , primePow ) { if ( pos == primePow . length ) { return getSum ( arr ) ; } let res = Number . MAX_VALUE ; for ( let 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 ; } function minimumSumWithGivenLCM ( k , x ) { let primePow = primePower ( x ) ; let n = primePow . length ; let sum = 0 ; if ( n <= k ) { for ( let i = 0 ; i < primePow . length ; i ++ ) { sum += primePow [ i ] ; } sum += k - n ; } else { let arr = new Array ( k ) ; for ( let i = 0 ; i < k ; i ++ ) { arr [ i ] = 1 ; } sum = getMinSum ( 0 , arr , primePow ) ; } return sum ; } let k = 3 , x = 210 ; document . write ( minimumSumWithGivenLCM ( k , x ) ) ;