Minimize the cost of selecting two numbers whose product is X | Python3 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 . Print - 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
MAX = 10000 ; NEW_LINE max_prime = [ 0 ] * MAX ; NEW_LINE min_prime = [ 0 ] * MAX ; NEW_LINE def sieve ( n ) : NEW_LINE INDENT for i in range ( 2 , n ) : NEW_LINE INDENT if ( min_prime [ i ] > 0 ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT min_prime [ i ] = i ; NEW_LINE max_prime [ i ] = i ; NEW_LINE j = i + i ; NEW_LINE while ( j < n ) : NEW_LINE INDENT if ( min_prime [ j ] == 0 ) : NEW_LINE INDENT min_prime [ j ] = i ; NEW_LINE DEDENT max_prime [ j ] = i ; NEW_LINE j += i ; NEW_LINE DEDENT DEDENT DEDENT def findCost ( A , B , C , X ) : NEW_LINE INDENT sieve ( MAX ) ; NEW_LINE if ( X == 1 ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT min_cost = C + X ; NEW_LINE cost_for_prime = A ; NEW_LINE N = max_prime [ X ] ; NEW_LINE if ( N != X ) : NEW_LINE INDENT M = X // N ; NEW_LINE cost_for_prime += M ; NEW_LINE min_cost = min ( min_cost , cost_for_prime ) ; NEW_LINE DEDENT M = min_prime [ X ] ; NEW_LINE N = X // M ; NEW_LINE if ( N != min_prime [ N ] ) : NEW_LINE INDENT cost_for_comp = B + M ; NEW_LINE min_cost = min ( min_cost , cost_for_comp ) ; NEW_LINE DEDENT return min_cost ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = 7 ; B = 11 ; C = 2 ; X = 20 ; NEW_LINE print ( findCost ( A , B , C , X ) ) ; NEW_LINE DEDENT