GCD or the Greatest Common Divisor of two given numbers A and B is the highest number dividing both A and B completely, i.e., leaving remainder 0 in each case. LCM or the Least Common Multiple of two given numbers A and B is the Least number which can be divided by both A and B, leaving remainder 0 in each case.
The LCM of two numbers can be computed in Euclid’s approach by using GCD of A and B.
LCM(A, B) = (a * b) / GCD(A, B)
Examples:
Input : A = 20, B = 30
Output:
GCD = 10
LCM = 60Explanation:
The highest number which divides 20 and 30 is 10. So the GCD of 20, 30 is 10.
The lowest number that can be divided by 20 and 30, leaving remainder 0 is 60.
So the LCM of 20 and 30 is 60.Input : A= 33, B= 40
Output:
GCD = 1
LCM = 1320
Euclidean Algorithm for Computing GCD:
This approach of computing the GCD is based on the principle that the GCD of two numbers A and B remains the same even if the larger number is replaced by the modulo of A and B. In this approach, we perform the gcd operation on A and B repeatedly by replacing A with B and B with the modulo of A and B until the modulo becomes 0.
Below is the implementation of to find GCD and LCM of Two Numbers Using Euclid’s Algorithm:
Java
// Java program to compute// GCD of two numbers// using Euclid's algorithm import java.io.*; class GFG { // gcd method returns the GCD of a and b static int gcd(int a, int b) { // if b=0, a is the GCD if (b == 0) return a; // call the gcd() method recursively by // replacing a with b and b with // modulus(a,b) as long as b != 0 else return gcd(b, a % b); } // lcm() method returns the LCM of a and b static int lcm(int a, int b, int gcdValue) { return Math.abs(a * b) / gcdValue; } // Driver method public static void main(String[] args) { int a = 20, b = 30, gcdValue; gcdValue = gcd(a, b); // calling gcd() over System.out.println("GCD = " + gcdValue); // calling lcm() over integers 30 and 20 System.out.println("LCM = " + lcm(a, b, gcdValue)); }} |
GCD = 10 LCM = 60
