FIND THE LCM and GCD OF TWO NUMBERS

In this article, we are going to FIND THE LCM and GCD OF TWO NUMBERS.

GCD

The greatest common divisor(GCD) or the highest common factor(HCF) of two or more numbers is the highest common number that divides the given number exactly.

For example,

INPUT: 10 15
OUTPUT: 5

As 5 is the greatest common factor of 10 and 15.

APPROACH 1:

The gcd of two numbers will be always lesser than or equal to the smallest among the two numbers. So, traversing from 1 to the smallest among the two numbers by checking every number.

ALGORITHM

Step 1: Start

Step 2: Take two numbers as input.

Step 3: Assign zero to a temporary variable ‘gcd’.

Step 4: Traverse from 1 to the smallest of the two numbers and check for every number.

Step 5: While traversing, if any number satisfies, then equal it to the temporary variable gcd.

Step 6: Stop.

C++ Code:

#include <iostream>
using namespace std;

int main() {
   int a,b;
   cin>>a>>b;
   int gcd=0;
   for(int i = 1 ; i<=min(a,b) ; i++)
     if(a%i == 0 && b%i == 0) 
       gcd=i;
   cout<<gcd;
}

Python code:

a=int(input())
b=int(input())
gcd=0
for i in range(1,min(a,b)+1):
  if a%i == 0:
    if b%i == 0:
      gcd=i
print(gcd)

JAVA code:  

import java.util.*;

public class Main {
    public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      int a = s.nextInt();
      int b = s.nextInt();
      int gcd=0;
      for(int i = 1 ; i<=Math.min(a,b) ; i++)
      if (a%i == 0 && b%i == 0){
        gcd=i;
      }
      System.out.println(gcd);
  }
}

Input: 10 15

Output: 5

The time complexity of the code is O(min(a,b)).
The space complexity of the code is O(1).

APPROACH 2:

By using the euclidean algorithm which is used mainly for the calculation of GCD, is also an efficient method for the calculation of the GCD of two numbers.

ALGORITHM

Step 1: Start

Step 2: Recursively call the function while decreasing the larger number by dividing it by the smaller one.

Step 3: If anywhere any number results in zero, return the other number as GCD.

Step 4: Stop.

Let’s see the implementation of the euclidean algorithm in a recursive manner.

C++ Code:

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (a == 0)
        return b;
else
return gcd(b % a, a);
}

int main() {
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
}

Python code:

def gcd(a,b):
  if a==0:
    return b
  else:
    return gcd(b%a,a)
a = int(input())
b = int(input())
print(gcd(a,b))

JAVA code:  

import java.util.*;

public class Main {
  static int gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
  }
  public static void main(String args[]) {
    Scanner s = new Scanner(System.in);
    int a = s.nextInt();
    int b = s.nextInt();
    int n = gcd(a,b);
    System.out.println(n);
  }
}

Input: 10 15

Output: 5

The time complexity of the code is O(log(min(a,b))).
The space complexity of the code is O(1).

LCM

The abbreviation LCM stands for ‘Least Common Multiple‘. The least common multiple (LCM) of two numbers is the lowest possible number that can be divisible by both numbers. It can be calculated for two or more numbers as well. There are different methods to find the LCM of a given set of numbers. One of the quickest ways to find the LCM of two numbers is to use the prime factorization of each number and then the product of the highest powers of the common prime factors will be the LCM of those numbers.

INPUT: 10 15
OUTPUT: 30.

As 30 is the leastcommon multiple of 10 and 15.

Approach

We are having a simple math equation

GCD(a,b) * LCM(a,b) = a*b

So using this equation, we can find the lcm if we already know the gcd and its product.

We can find GCD using any of the above approaches.

C++ Code:

#include <iostream>
using namespace std;

int main() {
   int a,b;
   cin>>a>>b;
   int gcd=0;
   for(int i = 1 ; i<=min(a,b) ; i++)
     if(a%i == 0 && b%i == 0) 
       gcd=i;
   int lcm = a*b / gcd;
cout<<lcm;
}

Python code:

a=int(input())
b=int(input())
gcd=0
for i in range(1,min(a,b)+1):
  if a%i == 0:
    if b%i == 0:
      gcd=i
print(a*b/gcd)

JAVA code:  

import java.util.*;

public class Main {
    public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      int a = s.nextInt();
      int b = s.nextInt();
      int gcd=0;
      for(int i = 1 ; i<=Math.min(a,b) ; i++)
      if (a%i == 0 && b%i == 0){
        gcd=i;
      }
      System.out.println(a*b/gcd);
  }
}

Input: 10 15

Output: 30

The time complexity of the code is O(min(a,b)).
The space complexity of the code is O(1).