Divide N into K unique parts such that gcd of those parts is maximum | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxGCD ( int N , int K ) { int minSum = ( K * ( K + 1 ) ) / 2 ; if ( N < minSum ) return -1 ; int i = sqrt ( N ) ; int res = 1 ; while ( i >= 1 ) { if ( N % i == 0 ) { if ( i >= minSum ) res = max ( res , N / i ) ; if ( N / i >= minSum ) res = max ( res , i ) ; } i -- ; } return res ; } int main ( ) { int N = 18 , K = 3 ; cout << maxGCD ( N , K ) ; return 0 ; }