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!
