Java program to find the GCD of two numbers

Java program to find the GCD of two numbers. The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. One of the most efficient methods to find the GCD of two numbers is the Euclidean algorithm.

Here’s a Java program that prompts the user to enter two numbers and then calculates their GCD using the Euclidean algorithm.

import java.util.Scanner;

public class GCD {
    public static void main(String[] args) {
        // Create a Scanner object to read input from the user
        Scanner scanner = new Scanner(System.in);

        // Prompt the user to enter two numbers
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();
        
        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();

        // Calculate the GCD of the two numbers
        int gcd = findGCD(num1, num2);

        // Print the result
        System.out.println("The GCD of " + num1 + " and " + num2 + " is " + gcd + ".");
    }

    // Method to find the GCD using the Euclidean algorithm
    public static int findGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Explanation of the Code (Java program to find the GCD of two numbers)

Let’s break down the program step-by-step to understand how it works.

Importing the Scanner Class: We import the Scanner class from the java.util package to read input from the user.

import java.util.Scanner;

2. Creating the Main Class: We create a public class named GCD. In Java, the class name should match the filename.

public class GCD {

3. Main Method: The main method is the entry point of the program. Inside this method, we will write the code to find the GCD of two numbers.

public static void main(String[] args) {

4. Creating a Scanner Object: We create a Scanner object to read input from the user.

Scanner scanner = new Scanner(System.in);

5. Reading Input from the User: We prompt the user to enter two numbers and store these values in variables.

System.out.print("Enter the first number: ");
int num1 = scanner.nextInt();

System.out.print("Enter the second number: ");
int num2 = scanner.nextInt();

6. Calculating the GCD: We call the findGCD method to calculate the GCD of the two numbers. The result is stored in a variable gcd.

int gcd = findGCD(num1, num2);

7. Printing the Result: We print the GCD of the two numbers.

System.out.println("The GCD of " + num1 + " and " + num2 + " is " + gcd + ".");

8. Method to Find the GCD: The findGCD method uses the Euclidean algorithm to calculate the GCD of two numbers. The algorithm works by repeatedly replacing the larger number by its remainder when divided by the smaller number until the remainder is zero. The last non-zero remainder is the GCD.

public static int findGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Explanation of the `findGCD` Method

Loop to Find GCD: The while loop continues as long as b is not zero. In each iteration, we update b to be the remainder of a divided by b, and update a to be the previous value of b.

while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
}

2. Returning the GCD: When b becomes zero, a contains the GCD of the original two numbers. We return a.

return a;

Running the Program

To run the program, follow these steps:

Save the code in a file named GCD.java.
Open a command prompt or terminal and navigate to the directory where you saved the file.
Compile the program using the following command:

javac GCD.java

4. Run the compiled program using the following command:

5. Follow the prompt to enter two numbers. The program will display their GCD.

Example Output

If you run the program and enter 56 and 98 as the numbers, the output will be:

Enter the first number: 56
Enter the second number: 98
The GCD of 56 and 98 is 14.

What did we learn from this article?

Finding the GCD of two numbers is a fundamental exercise that helps in understanding loops and arithmetic operations in programming. This Java program demonstrates how to implement the Euclidean algorithm to find the GCD efficiently. By practicing such basic programs, you can strengthen your problem-solving skills and gain confidence in your ability to write efficient Java code. Keep practicing and exploring more problems to enhance your programming skills.

Top 100 Java Programs: Click Here

Are you looking for a job: Click Here