Divide N into K unique parts such that gcd of those parts is maximum | Python3 implementation of the approach ; Function to calculate maximum GCD ; Minimum possible sum for K unique positive integers ; It is not possible to divide N into K unique parts ; All the factors greater than sqrt ( N ) are complementary of the factors less than sqrt ( N ) ; If i is a factor of N ; Driver code
from math import sqrt , ceil , floor NEW_LINE def maxGCD ( N , K ) : NEW_LINE INDENT minSum = ( K * ( K + 1 ) ) / 2 NEW_LINE if ( N < minSum ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT i = ceil ( sqrt ( N ) ) NEW_LINE res = 1 NEW_LINE while ( i >= 1 ) : NEW_LINE INDENT if ( N % i == 0 ) : NEW_LINE INDENT if ( i >= minSum ) : NEW_LINE INDENT res = max ( res , N / i ) NEW_LINE DEDENT if ( N / i >= minSum ) : NEW_LINE INDENT res = max ( res , i ) NEW_LINE DEDENT DEDENT i -= 1 NEW_LINE DEDENT return res NEW_LINE DEDENT N = 18 NEW_LINE K = 3 NEW_LINE print ( maxGCD ( N , K ) ) NEW_LINE