Minimize the cost of selecting two numbers whose product is X | Javascript implementation of the above approach ; max_prime [ i ] represents maximum prime number that divides the number i ; min_prime [ i ] represents minimum prime number that divides the number i ; Function to store the minimum prime factor and the maximum prime factor in two arrays ; Check for prime number if min_prime [ i ] > 0 , then it is not a prime number ; If i is a prime number , then both minimum and maximum prime numbers that divide the number is the number itself ; If this number is being visited for first time then this divisor must be the smallest prime number that divides this number ; The last prime number that divides this number will be maximum . ; Function to minimize the cost of finding two numbers for every number such that the product of those two is equal to X ; Pre - calculation ; If X == 1 , then there is no way to find N and M . Prlet - 1 ; Case 3 is always valid and cost for that is C + X C for choosing 1 and M = X / 1 ; Case 1 N is prime , first number cost is fixed N is max_prime number divides this number ; If X is prime then the maximum prime number is the number itself . For this case , M becomes 1 and this shouldn 't be considered. ; Find M for this case ; Add cost for the second number also ; Update min_cost , if the cost for prime is minimum ; Case 2 If N is composite For this find the minimum prime number that divides A [ i ] and consider this as M ; Find N for that number ; Check if this number is composite or not if N is prime then there is no way to find any composite number that divides X If N = min_prime [ N ] then N is prime ; Update min_cost , if the cost for the composite is minimum ; Driver Code
let MAX = 1000 ; let max_prime = Array . from ( { length : MAX } , ( _ , i ) => 0 ) ; let min_prime = Array . from ( { length : MAX } , ( _ , i ) => 0 ) ; function sieve ( n ) { for ( let i = 2 ; i < n ; ++ i ) { if ( min_prime [ i ] > 0 ) { continue ; } min_prime [ i ] = i ; max_prime [ i ] = i ; let j = i + i ; while ( j < n ) { if ( min_prime [ j ] == 0 ) { min_prime [ j ] = i ; } max_prime [ j ] = i ; j += i ; } } } function findCost ( A , B , C , X ) { sieve ( MAX ) ; let N , M ; if ( X == 1 ) { return - 1 ; } let min_cost = C + X ; let cost_for_prime = A ; N = max_prime [ X ] ; if ( N != X ) { M = X / N ; cost_for_prime += M ; min_cost = Math . min ( min_cost , cost_for_prime ) ; } M = min_prime [ X ] ; N = X / M ; if ( N != min_prime [ N ] ) { let cost_for_comp = B + M ; min_cost = Math . min ( min_cost , cost_for_comp ) ; } return min_cost ; } let A = 7 , B = 11 , C = 2 , X = 20 ; document . write ( findCost ( A , B , C , X ) ) ;