How to Find the GCD of Two Numbers in Java: A Comprehensive Guide

The Greatest Common Divisor (GCD) of two numbers is the most significant number that divides both numbers completely. Hence, it does not leave a remainder. It’s also known as the Highest Common Factor (HCF). For example: 

Find the GCD of 28 and 42.

Step-wise approach 

Step 1: List all divisors

• Divisors of 28: 1, 2, 4, 7, 14, 28
• Divisors of 42: 1, 2, 3, 6, 7, 14, 21, 42

Step 2: Find the common divisors

• Common divisors: 1, 2, 7, 14

Step 3: Pick the greatest common divisor

• GCD = 14

The GCD can also be found by multiplying the Prime factors of two numbers: 

‍Again, using the same numbers as earlier, find the GCD of 28 and 42.

‍Step 1: List the prime factors of each number

• Prime factors of 28: 2 × 2 × 7
• Prime factors of 42: 2 × 3 × 7

Step 2: Identify the common factors

• Common factors: 2 × 7

Step 3: Multiply the common factors

• GCD = 2 × 7 = 14

There are multiple approaches to find the GCD of two numbers in Java. Each method is suited for different scenarios and problems. Here’s a detailed look at the most popular methods:

GCD of More Than Two Numbers

The Greatest Common Divisor (GCD) of three or more numbers can be determined by finding the largest integer that divides all the numbers without leaving a remainder, just like the others. With an algorithm, this means identifying the product of the prime factors that are common to all given numbers. But rather than factoring each number, the GCD can be computed by repeatedly applying the Euclidean algorithm to pairs of numbers.

It can be said that : GCD(a, b, c) = GCD(a, GCD(b, c))

It means we first find the GCD of any two numbers, then use that result to find the GCD with the next number. The order in which pairs are chosen does not affect the final result, as GCD operations are associative. 

Pseudocode

1. Start

2. Define a function findGCD(a, b) to compute the GCD of two numbers using the Euclidean algorithm: While b is not 0:

• Set temp = b, Set b = a % b, Set a = temp
• Return a as the GCD

3. Define a function findGCDofArray(arr) to compute the GCD of an array of numbers:

• Set result = arr[0] (initialize with the first number in the array).

Loop through the array from index 1: Update result by calling findGCD(result, arr[i]). If result == 1, return 1 (no need to check further).

• Return the final result as the GCD of the array.

4. In the main() method:

• Create a Scanner object to read input.
• Ask the user for the number of elements in the array.
• Initialize an array numbers[] with the given size.
• Prompt the user to input the elements into the array.
• Call findGCDofArray(numbers) to find the GCD of the array.
• Print the result.
• Close the scanner.

5. End

‍Code 

import java.util.Scanner;
 
class Main {
    // Function to find GCD of two numbers 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;
    }
 
    // Function to find GCD of an array of numbers
    public static int findGCDofArray(int[] arr) {
        int result = arr[0]; // Start with the first number
        for (int i = 1; i < arr.length; i++) {
        	result = findGCD(result, arr[i]);
        	if (result == 1) { // If GCD becomes 1, no need to continue
            	return 1;
        	}
        }
        return result;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        // Taking input for the number of elements
        System.out.print("Enter the number of elements: ");
        int n = scanner.nextInt();
        int[] numbers = new int[n];
 
        // Taking input for the array elements
        System.out.println("Enter the numbers:");
        for (int i = 0; i < n; i++) {
        	numbers[i] = scanner.nextInt();
        }
 
        // Finding the GCD of the array
        int gcd = findGCDofArray(numbers);
 
        // Displaying the result
        System.out.println("The GCD of the given numbers is: " + gcd);
       
        scanner.close();
    }
}

How the Code Works

Step 1: The program asks the user to enter the number of elements in the array.

Step 2: The user inputs the numbers, which are stored in an array.

Step 3: The program calculates the GCD of the entire array using findGCDofArray(), which applies the Euclidean algorithm iteratively by calling findGCD(a, b).

Step 4: The result is printed on the screen.

Output

Enter the number of elements: 3
Enter the numbers:
5 10 15
The GCD of the given numbers is: 5
 
=== Code Execution Successful ===

Complexity

Time Complexity: O(log(min(a, b)))

Space Complexity: O(n log M), where n is the number of elements in the array, and M is the maximum number in the array.

Now that we know how some of these methods for GCD Java work, let’s look at some examples: 

1. Program Using the Basic Euclidean Algorithm

In the basic Euclidean algorithm, you will repeatedly subtract the smaller number from the larger one until the two numbers become equal. For example, if you want to find the GCD of 28 and 16, you would subtract 16 from 28, which is 12, and then subtract 12 from 16, which is 4. This subtraction continues until the remainder is zero, and the algorithm finally gives 4 as the GCD. The method is very simple to understand and implement but it can be slow for large numbers due to so many subtraction steps.Now let’s look at the GCD of two numbers in Java using the basic Euclidean algorithm: 

‍Pseudocode: 

‍1. Start

2. In the main() method:

• Create a Scanner object to read input.
• Prompt the user to enter the first number and store it in num1.
• Prompt the user to enter the second number and store it in num2.
• Call findGCD(num1, num2) to compute the GCD.
• Display the result.

3. Define the function findGCD(a, b) using the Euclidean Algorithm:

• While a is not equal to b:
• If a > b, update a = a - b.
• Else, update b = b - a.
• Return a (or b, as both will be equal).

4. End

‍Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

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

        // Calculate GCD using the Euclidean Algorithm
        int gcd = findGCD(num1, num2);

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

    // Method to calculate GCD using the Basic Euclidean Algorithm
    public static int findGCD(int a, int b) {
        while (a != b) {
            if (a > b) {
                a = a - b;
            } else {
                b = b - a;
            }
        }
        return a; // or return b, as both will be equal at this point
    }
}

How the Code Works

Step 1: The program asks the user to input two integers (num1 and num2).

Step 2: These two numbers are passed to the findGCD method, which uses the basic Euclidean algorithm to calculate the GCD.

Step 3: Inside the method, a while loop runs until both numbers become equal. If a is greater than b, the program subtracts b from a. Otherwise, it subtracts a from b.

Step 4: When the loop ends, both numbers are the same, and that value is returned as the GCD.

Step 5: The main method then prints the GCD to the console.

Output

Enter the first number: 
28
Enter the second number: 
16
The GCD of 28 and 16 is: 4

=== Code Execution Successful ===

Complexity

Time Complexity: O(min(a,b))) - The number of iterations depends on the smaller of the two numbers, as each iteration reduces the larger number by the smaller one. Hence, this method is unsuitable for large numbers of people.

Space Complexity: O(1) – The algorithm uses only constant space. 

Advantages

• The method is easy to understand and implement compared to other methods.
• It uses only subtraction, which is helpful in cases where division or modulus operations are expensive.
• Works efficiently for small numbers.

2. Program Using the Optimized Euclidean Algorithm

This approach improves on the basic algorithm discussed above. It replaces subtraction with the modulo operation. So, instead of repeatedly subtracting, the more significant number is divided by the smaller number, and the remainder is used for the next iteration. For example, finding the GCD of 28 and 16 involves calculating 28 % 16, and the remainder is 12. Then 16 is divided by 12, for which the reminder is 4. This continues until the remainder is zero. This method is faster and more efficient, especially for larger numbers.

‍Pseudocode 

‍1. Start

2. In the main() method:

• Create a Scanner object to read input.
• Prompt the user to enter the first number and store it in num1.
• Prompt the user to enter the second number and store it in num2.
• Call findGCD(num1, num2) to compute the GCD.
• Display the result.
• Close the scanner.

3. Define the function findGCD(a, b) using the optimized Euclidean Algorithm:While b is not 0:

• Store b in temp.
• Update b = a % b.
• Update a = temp.
• Return a as the GCD.

4. End

‍Code

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Taking input for 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 GCD using the Optimized Euclidean Algorithm
        int gcd = findGCD(num1, num2);

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

        scanner.close();
    }

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

How the Code Works

Step 1: The program prompts the user to enter two integers, num1 and num2. These numbers will be used to calculate the GCD.

Step 2: The findGCD() method is called with num1 and num2 as arguments. Inside the method, the algorithm uses the Optimized Euclidean Algorithm:

• The while loop runs as long as b (the second number) is not zero.
• In each iteration, the remainder of a divided by b is stored in b, and the value of b is assigned to a.
• This process continues until the remainder (b) becomes zero, at which point a holds the GCD.

Step 3: Once the GCD is found (when b is zero), the program prints the GCD of num1 and num2.

‍Step 4: End of Program

‍Output

Enter the first number: 28
Enter the second number: 16
The GCD of 28 and 16 is: 4

=== Code Execution Successful ===

Complexity 

Time Complexity: O(log(min(a, b)))

Space Complexity: O(1)

Advantages

• It is more efficient than the basic Euclidean algorithm since it reduces the number of iterations significantly.
• Works in O(log(min(a, b))) time complexity, therefore it is faster for large numbers.
• The method uses the modulus operator instead of repeated subtraction.
• It works well when performance is a concern, especially for large numbers.

3. Program Using Recursion

The recursive method better implements the Euclidean algorithm (modulo version). Instead of using loops, the function calls itself with updated parameters until the base condition is met; that is, the remainder becomes zero. For example, if the GCD of 28 and 16 is calculated recursively, the function will call itself with (16, 28 % 16), then (12, 16 % 12), and so on. This approach is concise and preferred when recursion is a natural fit for the problem.

‍Pseudocode

‍1. Start

2. Define the recursive function findGCD(a, b):

• If b is 0, return a (base case).
• Otherwise, return findGCD(b, a % b) (recursive call).

3. In the main() method:

• Create a Scanner object to read input.
• Prompt the user to enter the first number and store it in num1.
• Prompt the user to enter the second number and store it in num2.
• Call findGCD(num1, num2) to compute the GCD.
• Display the result.
• Close the scanner.

4. End

Now let’s see how the greatest common divisor Java program works in recursion: 

‍Code

import java.util.Scanner;

class Main {
    // Recursive method to find GCD
    public static int findGCD(int a, int b) {
        if (b == 0) {
            return a;  // Base case: GCD is found when b is 0
        }
        return findGCD(b, a % b);  // Recursive call with new values
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Asking user for input
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();

        // Calling the recursive method to calculate GCD
        int gcd = findGCD(num1, num2);

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

How the Code Works

Step 1: The program asks the user to input two integers, num1 and num2.

Step 2: The program calls the findGCD() method to compute the GCD. Inside findGCD(), it checks if the second number (b) is zero. If b is zero, a is returned as the GCD. If b is not zero, the method recursively calls itself with the values b and a % b (the remainder when a is divided by b).

Step 3: Once the GCD is found (when b becomes zero), the result is displayed.

Output

Enter the first number: 34
Enter the second number: 48
The GCD of 34 and 48 is: 2

=== Code Execution Successful ===

Complexity 

Time Complexity: the complexity is O(log(min(a, b))) because each recursive step reduces the size of the problem logarithmically. 

Space Complexity: The space complexity is O(log(min(a, b))). 

Advantage

• The code is shorter, cleaner, and easier to understand.
• Eliminates the need for explicit loops, making it useful in functional programming scenarios.
• Uses O(log(min(a, b))) time complexity, similar to the optimized Euclidean algorithm.
• Useful when reducing code complexity is more important than avoiding function calls.

4. Program Using Java's BigInteger Class

The BigInteger class in Java is the best option when working with extremely large numbers. It provides a built-in gcd() method that computes the GCD directly without requiring manual implementation. This highly optimised method can handle numbers much larger than Java’s primitive types allow. For example, the GCD of two BigInteger numbers, such as 123456789123456789 and 987654321987654321, can be calculated with just a single method call. This approach is best for cases with large numbers which require fast computation. 

‍Pseudocode

‍1. Start

2. In the main() method:

• Create a Scanner object to read input.
• Prompt the user to enter the first number and store it as a string in num1Str.
• Prompt the user to enter the second number and store it as a string in num2Str.
• Convert num1Str to a BigInteger and store it in num1.
• Convert num2Str to a BigInteger and store it in num2.
• Compute the GCD using num1.gcd(num2) and store the result in gcd.
• Display the result.
• Close the scanner.

3. End

Now let’s see how to find the GCD of large numbers: 

‍Code

import java.math.BigInteger;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Asking user for input
        System.out.print("Enter the first number: ");
        String num1Str = scanner.nextLine();
        System.out.print("Enter the second number: ");
        String num2Str = scanner.nextLine();

        // Converting input strings to BigInteger
        BigInteger num1 = new BigInteger(num1Str);
        BigInteger num2 = new BigInteger(num2Str);

        // Finding the GCD using the gcd method of BigInteger
        BigInteger gcd = num1.gcd(num2);

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

How the Code Works

Step 1: The program asks the user to input two large numbers. Since BigInteger handles very large integers, the user can input numbers of any size. The input is taken as strings because BigInteger works with string inputs.

Step 2: The program converts the input strings into BigInteger objects using the BigInteger constructor.

Step 3: To find GCD using BigInteger's method, the program calls the gcd() method of the BigInteger class. It calculates the GCD of two BigInteger numbers.

Step 4: Once the GCD is calculated, the result is displayed on the screen.

Output

Enter the first number: 123456789123456789
Enter the second number: 987654321987654321
The GCD of 123456789123456789 and 987654321987654321 is: 9000000009

=== Code Execution Successful ===

Complexity

Time Complexity: The time complexity of the gcd() method in BigInteger is O(log(min(a, b))), similar to the Euclidean algorithm.

Space Complexity: The space complexity is O(log(min(a, b))). BigInteger objects require space proportional to the size of the numbers.

Advantage

• The program can handle very large numbers that cannot fit into primitive types like int or long.
• The gcd() method in BigInteger is highly optimised and built-in.
• Eliminates the need for custom implementations of the GCD algorithm.

5. Program Using Iterative Loops 

This method checks every possible divisor of the two numbers by iterating from 1 to the smaller of the two numbers. The largest divisor, which divides both numbers, becomes the GCD. For example, to find the GCD of 28 and 16, this method will check divisors like 1, 2, 4, and so on, identifying 4, then eventually identifying 4 as the largest common divisor. The method is less efficient for large inputs due to the high number of iterations.

‍Pseudocode 

‍1. Start

2. In the main() method:

• Create a Scanner object to read input.
• Prompt the user to enter the first number and store it in num1.
• Prompt the user to enter the second number and store it in num2.
• Call findGCD(num1, num2) to compute the GCD.
• Display the result.
• Close the scanner.

3. Define the function findGCD(a, b):

• While b is not 0:
• Store b in temp.
• Update b = a % b.
• Update a = temp.
• Return a as the GCD.

4. End

‍Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Taking input from the user
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();

        // Finding the GCD using an iterative loop
        int gcd = findGCD(num1, num2);

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

        scanner.close();
    }

    // Method to calculate GCD using an iterative loop
    public static int findGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

How the Code Works

Step 1: The program prompts the user to enter two integers. The input is taken using the Scanner class and stored as integer variables.

Step 2: The program calls the findGCD method, passing the two input numbers as arguments.

Step 3: Inside the findGCD method, the program uses an iterative loop to apply the Euclidean algorithm. It repeatedly updates a and b using the formula a = b and b = a % b until b becomes 0.

Step 4: When b reaches 0, the remaining value of a is the GCD of the two numbers. The method returns this value.

Step 5: The program prints the calculated GCD on the screen, displaying the result to the user. 

Output

Enter the first number: 5
Enter the second number: 10
The GCD of 5 and 10 is: 5

=== Code Execution Successful ===

Complexity

Time Complexity: O(log(min(a,b))) – the time is logarithmic because with each step, the size of the numbers decreases approximately by half.

Space Complexity: O(1) - The algorithm uses constant space.

Advantage:

• It avoids recursive function calls, reducing the risk of stack overflow for very large numbers.
• More memory-efficient as it does not require extra space for recursion call stacks.
• Good for scenarios where recursion is not preferred.

6. Using Java For Loop

The for loop approach iterates through a range of numbers from 1 to the smaller of the two input numbers. During each iteration, it checks if the current number divides both numbers with a zero remainder. If it does, the value of the divisor is stored as the current GCD. At the end of the loop, the highest common divisor is identified and displayed as the result. This method is straightforward and helps beginners understand the concept of looping while solving a problem.

‍Pseudocode

‍1. Start

2. In the main() method:

• Create a Scanner object to read input.
• Prompt the user to enter the first number and store it in num1.
• Prompt the user to enter the second number and store it in num2.
• Call findGCD(num1, num2) to compute the GCD.
• Display the result.
• Close the scanner.

3. Define the function findGCD(a, b):

• Initialize gcd to 1.
• Iterate i from 1 to min(a, b):
• If both a and b are divisible by i, update gcd to i.
• Return gcd as the final result.

4. End

‍Code

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        // Taking input from the user
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();
 
        // Finding GCD using a for loop
        int gcd = findGCD(num1, num2);
 
        // Display the result
        System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + gcd);
 
        scanner.close();
    }
 
    // Method to find GCD using a for loop
    public static int findGCD(int a, int b) {
        int gcd = 1; // Initialize GCD to 1
        for (int i = 1; i <= Math.min(a, b); i++) {
        	if (a % i == 0 && b % i == 0) {
            	gcd = i; // Update GCD when a common divisor is found
        	}
        }
        return gcd;
    }
}

How the Code Works

Step 1: The program asks the user to input two numbers using Scanner.

Step 2: The findGCD method is called, which uses a for loop to find the GCD.

Step 3: The loop runs from 1 to min(a, b), checking if both numbers are divisible by i.

Step 4: The highest common divisor found during iteration is stored in gcd.

Step 5: The program prints the calculated GCD.

Output

Enter the first number: 50
Enter the second number: 10
The GCD of 50 and 10 is: 10

=== Code Execution Successful ===

Complexity

Time Complexity: O(min(a,b)) - The loop runs up to the smaller of the two numbers.

Space Complexity: O(1) - Only a few integer variables are used.

Advantage:

• The approach is simple to implement and understand for beginners.
• It works well for small numbers where performance is not a major concern.
• It avoids recursion and is easier to debug.

7. Using Java While Loop 

The while loop method finds the GCD by repeatedly applying the Euclidean algorithm (subtraction or modulo operation) until one of the numbers becomes zero. In this approach, the loop continues to execute as long as both numbers are non-zero and their values are updated after each iteration. Once the loop ends, the remaining non-zero value is the GCD.

‍Pseudocode

‍1. Start

2. In the main() method:

• Create a Scanner object to read input.
• Prompt the user to enter the first number and store it in num1.
• Prompt the user to enter the second number and store it in num2.
• Call findGCD(num1, num2) to compute the GCD.
• Display the result.
• Close the scanner.

3. Define the function findGCD(a, b):

• Initialize i to the smaller of a and b.
• While i is greater than 0:
• If both a and b are divisible by i, return i as the GCD.
• Decrease i by 1.
• If no common divisor is found, return 1.

4. End

‍Code

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        // Taking input from the user
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();
 
        // Finding GCD using a while loop
        int gcd = findGCD(num1, num2);
 
        // Display the result
        System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + gcd);
 
        scanner.close();
    }
 
    // Method to find GCD using a while loop
    public static int findGCD(int a, int b) {
        int i = Math.min(a, b); // Start from the smaller number
 
        while (i > 0) {
        	if (a % i == 0 && b % i == 0) {
            	return i; // Return the first common divisor found
        	}
      	  i--; // Decrease i until GCD is found
        }
        return 1; // If no GCD is found, return 1
    }
}

How the Code Works

Step 1: The program prompts the user to enter two numbers using Scanner.

Step 2: The findGCD method initialises i with the minimum of the two numbers.

Step 3: A while loop runs, checking if i divides both numbers.

Step 4: The first valid divisor (largest common divisor) is returned as the GCD.

Step 5: The program prints the calculated GCD.

Output

Enter the first number: 55
Enter the second number: 35
The GCD of 55 and 35 is: 5

=== Code Execution Successful ===

Complexity

Time Complexity: O(min(a,b))

Space Complexity: O(1) 

Advantage:

• More efficient than a for loop because it stops as soon as the GCD is found.
• Reduces unnecessary iterations compared to looping through all possible divisors.
• Avoids recursion, making it more memory-efficient.

It’s important to remember that Even if one or both numbers are negative, the GCD remains the same. That’s because GCD is based on the absolute values of the numbers.
Now let’s look at the GCD Java code when numbers are negative: 

Pseudocode: 

1. Start

2. In the main() method:

• Create a Scanner object to read input.
• Prompt the user to enter the first number and store it in num1.
• Prompt the user to enter the second number and store it in num2.
• Call findGCD(num1, num2) to compute the GCD.
• Display the result.
• Close the scanner.

3. Define the function findGCD(num1, num2):

• Convert num1 and num2 to their absolute values.
• While num2 is not zero:
• Store the value of num2 in a temporary variable temp.
• Set num2 to num1 % num2.
• Assign num1 the value of temp.
• When the loop ends, return num1 as the GCD.

4. End

‍Code

import java.util.Scanner;

class Main {

    // User-defined method to find GCD using Euclidean Algorithm by Iteration
    public static int findGCD(int num1, int num2) {
        // Make both numbers positive as GCD is the same for positive and negative numbers
        num1 = Math.abs(num1);
        num2 = Math.abs(num2);

        // Continue the loop until num2 becomes zero
        while (num2 != 0) {
            // Store the remainder of num1 divided by num2
            int temp = num2;
            num2 = num1 % num2;  // Update num2 to remainder
            num1 = temp;  // Update num1 to the old value of num2
        }
        // When the loop ends, num1 holds the GCD
        return num1;  // Return the GCD
    }

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

        // Ask the user for two numbers
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();

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

        // Call the user-defined method to find the GCD using Euclidean Algorithm
        int gcd = findGCD(num1, num2);
        
        // Print the value of the GCD
        System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + gcd);
        
        // Close the scanner
        scanner.close();
    }
}

How the Code Works

1. User Input: The program asks the user to input two numbers (which can be both positive or negative).
2. Handle Negative Numbers: The Math.abs() method is used to convert both numbers to their absolute (positive) values since the GCD is the same for both positive and negative numbers.
3. Euclidean Algorithm by Iteration: The method then uses the Euclidean Algorithm by Iteration to compute the GCD.
4. Print Result: The program prints the GCD of the two numbers.

Output

Enter the first number: 55
Enter the second number: -35
The GCD of 55 and -35 is: 5

=== Code Execution Successful ===

Complexity

Time Complexity: O(log(min(num1, num2))) - The Euclidean algorithm results in a logarithmic time complexity.

Space Complexity: O(1) - The algorithm uses a constant amount of space.

Complexity is how the performance of an algorithm changes as the size of the input increases. It helps us understand how efficiently an algorithm works in terms of time, like how long it takes and space, such as how much memory it uses. We can compare different methods and choose the most optimal approach for a given problem by analysing the time and space complexity.

Time Complexity

The time complexity of all the methods discussed has logarithmic time complexity, except for the iteration method. 

Space Complexity

Space complexity is the memory an algorithm uses to solve a problem as the input size grows. It includes both the memory used by the algorithm's variables and the memory required for other tasks. An algorithm with low space complexity is more efficient. It is best when dealing with large datasets as it uses less memory to perform computations.

Here are some common mistakes you should look out for in the greatest common divisor Java programs: 

• Forgetting to handle edge cases: One common mistake is not considering special cases, like when one or both numbers are zero. For example, the GCD of (0, x) is x, not zero. This can generate incorrect results if not handled properly in the program.
• Not accounting for negative numbers: The GCD is calculated for positive integers. So if the input numbers are negative, they should first be converted to the positive value. If not, the algorithm may not work as intended with negative values.‍
• Misusing the modulus operator: In the Euclidean algorithm, the modulus operator is crucial for finding the remainder in each iteration. If it's applied incorrectly the algorithm may not converge correctly to the GCD. That can give erroneous results. It's essential to ensure that each division step correctly calculates the remainder and continues the process until the remainder is zero.

The GCD method is necessary for many mathematical operations:

• Cryptography: The GCD plays a crucial role in cryptography, especially in RSA encryption. It is used to compute the keys in the algorithm. It is used for the encryption and decryption of data using prime factors and their GCD.
• Fractions: GCD is necessary for simplifying fractions to their lowest terms. By finding the GCD of the numerator and denominator, we can divide both by this value and reduce the fraction to its simplest form.
• Modular Arithmetic: modular arithmetic is often used to solve problems involving remainders and divisions. The GCD helps effectively solve modular equations and find modular inverses.

Learning how to find the GCD of two numbers is very basic and helps build a strong foundation for tackling problems in coding. Understanding GCD and its different methods like loops, recursion, or algorithms like the Euclidean approach gives students insight into optimisation and mathematical thinking. To learn further, enroll into the CCBP 4.0 Academy Program.

1. What is the GCD of two numbers?

The GCD (Greatest Common Divisor) of two numbers is the largest number that can divide both numbers completely. It is also known as the Highest Common Factor (HCF).

2. Can the GCD of two negative numbers be different from two positive numbers?

No, the GCD of two negative numbers is the same as the GCD of their absolute values. GCD is always calculated using positive numbers.

3. What is the Euclidean algorithm?

The Euclidean algorithm is a method for finding the GCD of two numbers by repeatedly dividing the larger number by the smaller number.  It uses the remainder in the process until one of the numbers becomes zero.

4. How is the GCD used in real-world applications?

GCD is used in various applications like simplifying fractions, cryptography, and finding common denominators in mathematical problems. 

5. Which method is the most efficient for finding the GCD?

The Euclidean algorithm using iteration is the most efficient method for finding the GCD. That’s because it quickly reduces the size of the numbers and speeds up the computation.