Find GCD of N Numbers in Java

The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides two or more integers without leaving a remainder.

Key Points about GCD (Greatest Common Divisor)

1. Divides Exactly: GCD is the largest number that divides all the given numbers completely.
2. Mathematical Notation: For two numbers aaa and bbb, the GCD is denoted as gcd(a, b).
3. Special Cases:
   • GCD of any number with 0 is the number itself.
     Example: gcd(12,0)=12.
   • The GCD of two prime numbers is always 1.
     Example: gcd(7,13)=1.

Examples of Greatest Common Divisor (GCD)

Example 1: GCD of Two Numbers (12 and 18)

Find the GCD of 12 and 18:

1. List the factors of each number:
   • Factors of 12: 1,2,3,4,6,12
   • Factors of 18: 1,2,3,6,9,18
2. Identify the common factors: 1,2,3,6
3. The greatest common factor is 6.

gcd(12,18)=6

Example 2: GCD of More than Two Numbers (24, 36, and 48)

Find the GCD of 24, 36, and 48:

1. List the factors of each number:
   • Factors of 24: 1,2,3,4,6,8,12,24
   • Factors of 36: 1,2,3,4,6,9,12,18,36
   • Factors of 48: 1,2,3,4,6,8,12,16,24,48
2. Identify the common factors: 1,2,3,4,6,12
3. The greatest common factor is 12.

gcd(24,36,48)=12

How to Calculate GCD Using the Euclidean Algorithm?

The Euclidean Algorithm provides a fast way to calculate the GCD:

1. Start with two numbers a and b.
2. Replace a with b, and b with a%b (the remainder when a is divided by b).
3. Repeat until b=0. At this point, a is the GCD.

Example: GCD of 48 and 18

Step 1: a=48,b=18
48%18=12 (New values: a=18,b=12)
Step 2: 18%12=6 (New values: a=12,b=6)
Step 3: 12%6=0 (GCD is a=6)

Java Program: GCD of N Numbers

To find the GCD (Greatest Common Divisor) of N numbers in Java, we can use the Euclidean algorithm iteratively. Below is a Java program with detailed explanation.

package com.javacodepoint.array.basic;

import java.util.Scanner;

public class GCDofNNumbers {
	// Function to find GCD of two numbers
	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[] numbers) {
		int gcd = numbers[0]; // Start with the first number
		for (int i = 1; i < numbers.length; i++) {
			gcd = findGCD(gcd, numbers[i]);
		}
		return gcd;
	}

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

		// Input the size of the array
		System.out.print("Enter the number of elements: ");
		int n = scanner.nextInt();

		// Input the array elements
		int[] numbers = new int[n];
		System.out.println("Enter " + n + " numbers:");
		for (int i = 0; i < n; i++) {
			numbers[i] = scanner.nextInt();
		}

		// Find and print the GCD
		int gcd = findGCDofArray(numbers);
		System.out.println("The GCD of the given numbers is: " + gcd);
	}
}

OUTPUT:

Enter the number of elements: 4
Enter 4 numbers:
24
36
48
60
The GCD of the given numbers is: 12

Code Explanation

1. findGCD Function: Implements the Euclidean algorithm to find the GCD of two numbers.
2. findGCDofArray Function: Iteratively calculates the GCD of the array elements by reducing the array to a single GCD value.
3. Input and Output: The program reads an array of integers from the user, computes their GCD using the above functions, and prints the result.