This week's programming exercise is to

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 way to find GCF of two numbers is by using Euclid's algorithm. This is a recursive algorithm which 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:

You can see that the base case is when the second number become 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 become smaller due to the use of modulus operator.

##

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 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 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 which fully divides both 40 and 24.

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

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

##

Here is our sample Java program which finds the lowest common more multiple and a 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.

That's all about

The Coding Interview Bootcamp: Algorithms + Data Structures

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Java

**write a Java program to calculate GCF and LCM of two numbers**. The GCF, stands for Greatest common factor and LCM stands for Lowest common multiplier, both are popular mathematical operation 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 number, for example, if 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 way to find GCF of two numbers is by using Euclid's algorithm. This is a recursive algorithm which 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 become 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 become smaller due to the use of modulus operator.

##
__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 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 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 which fully divides both 40 and 24.

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

You can see that how 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 a 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.**Further Learning**The Coding Interview Bootcamp: Algorithms + Data Structures

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Java

**Programs from Interviews**for Practice- Design a Vending Machine in Java (answer)
- Print Fibonacci series (solution)
- Check if given number is Prime number (solution)
- Find if given String Palindrome (answer)
- Check if given Integer is Palindrome (answer)
- Check if 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)

## 2 comments :

Hi Javin

Above solution are good for small inputs but it will fail if we pass larger values.

Ahh, my mistake. Your solution is right. I was using int instead of long. :)

## Post a Comment