Given a number N, the task is to find two numbers a and b such that a + b = N and LCM(a, b) is minimum.
Examples:
Input: N = 15
Output: a = 5, b = 10
Explanation:
The pair 5, 10 has a sum of 15 and their LCM is 10 which is the minimum possible.Input: N = 4
Output: a = 2, b = 2
Explanation:Â
The pair 2, 2 has a sum of 4 and their LCM is 2 which is the minimum possible.
Approach: The idea is to use the concept of GCD and LCM. Below are the steps:
- If N is a Prime Number then the answer is 1 and N – 1 because in any other cases either a + b > N or LCM( a, b) is > N – 1. This is because if N is prime then it implies that N is odd. So a and b, any one of them must be odd and other even. Therefore, LCM(a, b) must be greater than N ( if not 1 and N – 1) as 2 will always be a factor.
- If N is not a prime number then choose a, b such that their GCD is maximum, because of the formula LCM(a, b) = a*b / GCD (a, b). So, in order to minimize LCM(a, b) we must maximize GCD(a, b).
- If x is a divisor of N, then by simple mathematics a and b can be represented as N / x and N / x*( x – 1) respectively. Now as a = N / x and b = N / x * (x – 1), so their GCD comes out as N / x. To maximize this GCD, take the smallest possible x or smallest possible divisor of N.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to check if number is// prime or notbool prime(int n){    // As 1 is neither prime    // nor composite return false    if (n == 1)        return false;Â
    // Check if it is divided by any    // number then it is not prime,    // return false    for (int i = 2; i * i <= n; i++) {        if (n % i == 0)            return false;    }Â
    // Check if n is not divided    // by any number then it is    // prime and hence return true    return true;}Â
// Function to find the pair (a, b)// such that sum is N & LCM is minimumvoid minDivisor(int n){Â
    // Check if the number is prime    if (prime(n)) {        cout << 1 << " " << n - 1;    }Â
    // Now, if it is not prime then    // find the least divisor    else {        for (int i = 2; i * i <= n; i++) {Â
            // Check if divides n then            // it is a factor            if (n % i == 0) {Â
                // Required output is                // a = n/i & b = n/i*(n-1)                cout << n / i << " "                     << n / i * (i - 1);                break;            }        }    }}Â
// Driver Codeint main(){Â Â Â Â int N = 4;Â
    // Function call    minDivisor(N);    return 0;} |
Java
// Java program for the above approachimport java.io.*;public class GFG{Â
// Function to check if number is// prime or notstatic boolean prime(int n){    // As 1 is neither prime    // nor composite return false    if (n == 1)        return false;Â
    // Check if it is divided by any    // number then it is not prime,    // return false    for (int i = 2; i * i <= n; i++)     {        if (n % i == 0)            return false;    }Â
    // Check if n is not divided    // by any number then it is    // prime and hence return true    return true;}Â
// Function to find the pair (a, b)// such that sum is N & LCM is minimumstatic void minDivisor(int n){Â
    // Check if the number is prime    if (prime(n))    {        System.out.print(1 + " " + (n - 1));    }Â
    // Now, if it is not prime then    // find the least divisor    else    {        for (int i = 2; i * i <= n; i++)        {Â
            // Check if divides n then            // it is a factor            if (n % i == 0)             {Â
                // Required output is                // a = n/i & b = n/i*(n-1)                System.out.print(n / i + " " +                                (n / i * (i - 1)));                break;            }        }    }}Â
// Driver Codepublic static void main(String[] args){Â Â Â Â int N = 4;Â
    // Function call    minDivisor(N);}}Â
// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approachÂ
# Function to check if number is# prime or notdef prime(n):         # As 1 is neither prime    # nor composite return false    if (n == 1):        return FalseÂ
    # Check if it is divided by any    # number then it is not prime,    # return false    for i in range(2, n + 1):        if i * i > n:            break        if (n % i == 0):            return FalseÂ
    # Check if n is not divided    # by any number then it is    # prime and hence return true    return TrueÂ
# Function to find the pair (a, b)# such that sum is N & LCM is minimumdef minDivisor(n):Â
    # Check if the number is prime    if (prime(n)):        print(1, n - 1)Â
    # Now, if it is not prime then    # find the least divisor    else:        for i in range(2, n + 1):            if i * i > n:                breakÂ
            # Check if divides n then            # it is a factor            if (n % i == 0):Â
                # Required output is                # a = n/i & b = n/i*(n-1)                print(n // i, n // i * (i - 1))                breakÂ
# Driver CodeN = 4Â
# Function callminDivisor(N)Â
# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;Â
class GFG{Â
// Function to check if number is// prime or notstatic bool prime(int n){         // As 1 is neither prime    // nor composite return false    if (n == 1)        return false;Â
    // Check if it is divided by any    // number then it is not prime,    // return false    for(int i = 2; i * i <= n; i++)     {        if (n % i == 0)            return false;    }Â
    // Check if n is not divided    // by any number then it is    // prime and hence return true    return true;}Â
// Function to find the pair (a, b)// such that sum is N & LCM is minimumstatic void minDivisor(int n){Â
    // Check if the number is prime    if (prime(n))    {        Console.Write(1 + " " + (n - 1));    }Â
    // Now, if it is not prime then    // find the least divisor    else    {        for(int i = 2; i * i <= n; i++)        {                         // Check if divides n then            // it is a factor            if (n % i == 0)             {                                 // Required output is                // a = n/i & b = n/i*(n-1)                Console.Write(n / i + " " +                             (n / i * (i - 1)));                break;            }        }    }}Â
// Driver Codepublic static void Main(String[] args){Â Â Â Â int N = 4;Â
    // Function call    minDivisor(N);}}Â
// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for the above approach   // Function to check if number is    // prime or not    function prime(n)    {             // As 1 is neither prime        // nor composite return false        if (n == 1)            return false;Â
        // Check if it is divided by any        // number then it is not prime,        // return false        for (i = 2; i * i <= n; i++)        {            if (n % i == 0)                return false;        }Â
        // Check if n is not divided        // by any number then it is        // prime and hence return true        return true;    }Â
    // Function to find the pair (a, b)    // such that sum is N & LCM is minimum    function minDivisor(n)    {Â
        // Check if the number is prime        if (prime(n))        {            document.write(1 + " " + (n - 1));        }Â
        // Now, if it is not prime then        // find the least divisor        else        {            for (i = 2; i * i <= n; i++)             {Â
                // Check if divides n then                // it is a factor                if (n % i == 0)                 {Â
                    // Required output is                    // a = n/i & b = n/i*(n-1)                    document.write(n / i + " " + (n / i * (i - 1)));                    break;                }            }        }    }Â
    // Driver Code        var N = 4;Â
        // Function call        minDivisor(N);Â
// This code is contributed by todaysgaurav</script> |
Output:Â
2 2
Time Complexity: O(sqrt(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
