Greatest Common Divisor | Euclid’s Algorithm for GCD | GCD of two numbers

Greatest Common Divisor (GCD)

Imagine you have a bag of marbles, and you want to share them with your friend in a way that each of you gets an equal number of marbles. The greatest common divisor (GCD) is like the largest number of marbles that both you and your friend can have while still having the same number each.

For example, let’s say you have 12 marbles, and your friend has 18 marbles. To find the GCD, you look at the numbers that can evenly divide both 12 and 18. In this case, 6 is the largest number that divides both 12 and 18 without leaving any marbles behind. So, the GCD of 12 and 18 is 6.

Here are examples of how to calculate the Greatest Common Divisor (GCD) using Java and Python:

Java Program:

import java.util.Scanner;

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

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

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

        int gcd = calculateGCD(num1, num2);
        System.out.println("GCD of " + num1 + " and " + num2 + " is " + gcd);
    }

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

Python Program:

def calculate_gcd(a, b):
    if b == 0:
        return a
    return calculate_gcd(b, a % b)

num1 = int(input("Enter the first number: "))
num2 = int(input("Enter the second number: "))

gcd = calculate_gcd(num1, num2)
print(f"GCD of {num1} and {num2} is {gcd}")

Both of these programs prompt the user to enter two numbers and then calculate and display the GCD using a recursive approach similar to Euclid’s Algorithm.

Euclid’s Algorithm for GCD

Euclid’s Algorithm is a clever way to find the GCD of two numbers. Here’s how it works:

1. Take the two numbers you want to find the GCD of, let’s say 48 and 64.
2. Divide the larger number by the smaller number: 64 ÷ 48 = 1 with a remainder of 16.
3. Now, replace the larger number with the smaller number (48) and the smaller number with the remainder (16).
4. Divide 48 by 16: 48 ÷ 16 = 3 with no remainder.
5. Now, replace the larger number with the smaller number (16) and the smaller number with the remainder (0, because there’s no remainder).
6. The last non-zero remainder you had is the GCD. In this case, it’s 16.

So, using Euclid’s Algorithm, the GCD of 48 and 64 is 16.

GCD of Two Numbers

Let’s take another example. Suppose you have 24 marbles, and your friend has 36 marbles. To find the GCD, you can use Euclid’s Algorithm:

1. Divide 36 by 24: 36 ÷ 24 = 1 with a remainder of 12.
2. Replace 36 with 24 and 24 with 12.
3. Divide 24 by 12: 24 ÷ 12 = 2 with no remainder.
4. Replace 24 with 12 and 12 with 0.
5. The last non-zero remainder is 12, which is the GCD.

So, the GCD of 24 and 36 is 12. This means you and your friend can evenly share their marbles in groups of 12 marbles each.

In a nutshell, the GCD is like finding the biggest shared factor between two numbers, and Euclid’s Algorithm is a smart way to figure it out by repeatedly dividing the larger number by the smaller one until there’s no remainder.

Here are Java and Python programs to find the Greatest Common Divisor (GCD) of two numbers using the Euclidean Algorithm:

Java:

import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();

        int gcd = findGCD(num1, num2);
        System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + gcd);
    }
}

Python:

def find_gcd(a, b):
    while b:
        a, b = b, a % b
    return a

num1 = int(input("Enter the first number: "))
num2 = int(input("Enter the second number: "))

gcd = find_gcd(num1, num2)
print(f"The GCD of {num1} and {num2} is: {gcd}")

These programs use the Euclidean Algorithm to calculate the GCD of two numbers. You input the two numbers, and the program calculates and prints the GCD.

Thank You!