How to calculate GCF and LCM of two numbers in Java? Example

This week's programming exercise is to write a Java program to calculate GCF and LCM of two numbers. The GCF stands for a Greatest common factor and LCM stands for Lowest common multiplier, both are popular mathematical operations and related to each other. The GCF is the largest number which divides both the number without leaving any remainder e.g. if two numbers are 24 and 40 then their GCF is 8 because 8 is the largest number which divides both 24 and 40 perfectly, without leaving any remainder. 

Similarly, LCM is the lowest number which is perfectly divisible by the two numbers, for example, if the given number is 40 and 24 then their LCM is 120 because this is the lowest number which is perfectly divisible by both 40 and 24.

Since, you can calculate LCM once you have GCF because LCM of two numbers a and b is nothing but a*b/GCF(a, b). So, in reality, we just need to calculate the greatest common divisor first and then we can find the lowest common multiplier.

One of the easiest ways to find the GCF of two numbers is by using Euclid's algorithm. This is a recursive algorithm that finds GCD of two numbers by a radical reduction in problem size by changing GCD(A, B) to GCD(B, A mod B)  where A>B.  The algorithm was proposed by Euclid about 2250 years ago. See Introduction to Algorithms to learn more about the Euclidian algorithm, an efficient way to find the GCD of two numbers.

Anyway, It works like below:

public static int GCF(int a, int b) {
    if (b == 0) {
      return a;
    } else {
      return (GCF(b, a % b));
    }
  }

You can see that the base case is when the second number becomes zero, in that case, GCF is nothing but the first number, otherwise, it keeps calling GCF() method using recursion but every time the second number becomes smaller due to the use of modulus operator.

Also, basic knowledge of essential data structure and algorithms is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms course on Udemy to improve their knowledge and algorithms skills.

How does Euclid's algorithm calculate GCD?

The Euclidean algorithm is easy to understand once you walk through the algorithm with an example and see the flowchart. Let's calculate GCD of 40 and 24 using the Euclidean algorithm, remember the first number should be greater than the second in order to be used with this algorithm.

The first step is to check if the second number is zero, in that case obviously GCD is the first number. If that's not the case then the second number becomes the first and a mod b becomes the second number e.g. now we need to calculate GCD of 24 and 40 % 24 which is 16 i.e. GCD (24, 16) so our problem is now reduced.

Since the second number is still not zero, we move to the second step again and this time, the algorithm calculates GCD(16, 8) because 24 % 16 = 8. Since 8 is still not equal to zero, we again move to the next step and this time, the algorithm calculates GCD(8, 0) because 16 mod 8 = zero. Now, the second number is zero hence the first number is equal to GCD.

So, finally, the GCD of 40 and 24 is equal to 8 which is correct because it is the largest number that fully divides both 40 and 24.

Here is another example of Euclidean algorithm to calculate the greatest common divisor or greatest common factor:

You can see that how to step by step problem is reduced into calculating GCF of smaller numbers.

Java Program to calculate LCM and GCF of two numbers

Here is our sample Java program which finds the lowest common more multiple and the greatest common divisor of two numbers using Euclid's method. This program first calculates GCD or GCF using Euclidean Algorithm and then uses that method to calculate the LCM or lowest common multiplier.

If you want to learn more about essential programming algorithms, I suggest you read a good book on data structures and algorithms e.g. Introduction to Algorithms by Thomas H. Cormen, which explains key mathematical and programming algorithms in simple words.

Calculating LCM and GCD of two numbers in Java

public class LCM {

  public static void main(String[] args) {
    System.out.println("Welcome to Java Program to calculate 
                             LCM and GCF of two numbers");
    Scanner sc = new Scanner(System.in);

    System.out.println("Enter first number: ");
    int n1 = sc.nextInt();
    System.out.println("Enter second number: ");
    int n2 = sc.nextInt();

    int gcf = GCF(n1, n2);
    int lcm = LCM(n1, n2);

    System.out.println("The Greatest common divisor (GCF) of two numbers 
          are: "
        + gcf);
    System.out
        .println("The Lowest common multiplier (LCM) of two numbers are: "
            + lcm);

    sc.close();
  }

  /**
   * Java method to calculate lowest common multiplier of two numbers
   * 
   * @param a
   * @param b
   * @return LCM of two numbers
   */
  public static int LCM(int a, int b) {
    return (a * b) / GCF(a, b);
  }

  /**
   * Java method to calculate greatest common factor of two numbers
   * 
   * @param a
   * @param b
   * @return GCF of two numbers using Euclid's algorithm
   */
  public static int GCF(int a, int b) {
    if (b == 0) {
      return a;
    } else {
      return (GCF(b, a % b));
    }
  }

}

Output
Welcome to Java Program to calculate LCM and GCF of two numbers
Enter first number: 
40
Enter second number: 
24
The Greatest common divisor (GCF) of two numbers are: 8
The Lowest common multiplier (LCM) of two numbers are: 120

Welcome to Java Program to calculate LCM and GCF of two numbers
Enter first number: 
9
Enter second number: 
342
The Greatest common divisor (GCF) of two numbers are: 9
The Lowest common multiplier (LCM) of two numbers are: 342

That's all about how to find the GCF and LCM of two numbers in Java. It's very easy to do with Euclid's algorithm because once you have GCF, calculating LCM is nothing but a*b/GCF(a,b). If you want some more Java programs like this to practice and improve your coding sense and programming logic, check out the following list of programs from interviews.


Java Programs from Interviews for Practice

• Design a Vending Machine in Java  (answer)
• Print Fibonacci series (solution)
• Check if the given number is a Prime number (solution)
• Find if given String Palindrome (answer)
• Check if the given Integer is Palindrome (answer)
• Check if the given number is Armstrong number  (answer)
• How to do deadlock detection  (answer)
• How to calculate factorial  (answer)
• How to reverse String   (answer)
• Remove duplicates from an array   (answer)
• Printing patterns of stars  (answer)
• Implement binary search   (answer)
• Check if two Strings are Anagrams  (answer)