Find the pair (a, b) with minimum LCM such that their sum is equal to N

0 0 6 minutes read

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 not
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 minimum
void 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 Code
int main()
{
    int N = 4;
 
    // Function call
    minDivisor(N);
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
public class GFG{
 
// Function to check if number is
// prime or not
static 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 minimum
static 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 Code
public 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 not
def 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 minimum
def 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 Code
N = 4
 
# Function call
minDivisor(N)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to check if number is
// prime or not
static 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 minimum
static 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 Code
public 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 zambiatek!