Write a code to find a Greatest Common Divisor(GCD)

Greatest Common Divisor (GCD)

        The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both of them without leaving a remainder. It’s a fundamental concept in number theory and is used in various mathematical computations and algorithm optimizations. Below, we'll explore the solutions in C, C++, Java, and Python.

What is GCD?

        The GCD of two integers is the largest positive integer that divides both numbers without a remainder. For example, the GCD of 8 and 12 is 4.

Solutions:

        Now let’s look at how to calculate the GCD in different programming languages: Java, Python, C, and C++.

1. Java

        import java.util.Scanner;

        public class GCD {

            // Function to return the GCD of a and b

            public static int findGCD(int a, int b) {

                // Base case: if b is 0, GCD is a

                if (b == 0)

                    return a;

                // Recursive case: call findGCD with b and the remainder of a divided by b

                return findGCD(b, a % b);

            }    

            public static void main(String[] args) {

                Scanner scanner = new Scanner(System.in);

                System.out.print("Enter two integers: ");

                // Reading two integers from the user

                int a = scanner.nextInt();

                int b = scanner.nextInt();

                // Calling the GCD function

                int gcd = findGCD(a, b);

                // Printing the GCD

                System.out.println("GCD of " + a + " and " + b + " is: " + gcd);

                scanner.close();

            }

        }

2. Python

        # Function to return the GCD of a and b

        def find_gcd(a, b):

            # Base case: if b is 0, GCD is a

            if b == 0:

                return a

            # Recursive case: call find_gcd with b and the remainder of a divided by b

            return find_gcd(b, a % b)

        # Input from user

        a = int(input("Enter first number: "))

        b = int(input("Enter second number: "))

        # Calling the GCD function

        gcd = find_gcd(a, b)

        # Printing the GCD

        print(f"GCD of {a} and {b} is: {gcd}")

3. C++

       #include <iostream>

        using namespace std;

        // Function to return the GCD of a and b

        int findGCD(int a, int b) {

            // Base case: if b is 0, GCD is a

            if (b == 0)

                return a;

            // Recursive case: call findGCD with b and the remainder of a divided by b

            return findGCD(b, a % b);

        }

        int main() {

            int a, b;

            cout << "Enter two integers: ";

            // Reading two integers from the user

            cin >> a >> b;

    

            // Calling the GCD function

            int gcd = findGCD(a, b);

            // Printing the GCD

            cout << "GCD of " << a << " and " << b << " is: " << gcd << endl;

            return 0;

        }

4. C 

        #include <stdio.h>

        // Function to return the GCD of a and b

        int findGCD(int a, int b) {

            // Base case: if b is 0, GCD is a

            if (b == 0)

                return a;

            // Recursive case: call findGCD with b and the remainder of a divided by b

            return findGCD(b, a % b);

        }

        int main() {

            int a, b;

            printf("Enter two integers: ");

            // Reading two integers from the user

            scanf("%d %d", &a, &b);

            // Calling the GCD function

            int gcd = findGCD(a, b);

            // Printing the GCD

            printf("GCD of %d and %d is: %d\n", a, b, gcd);

           return 0;

        }

Explanation of Code:

Each code version defines a findGCD function to compute the GCD of two numbers using the Euclidean algorithm.

• Euclidean Algorithm: It’s an efficient method for computing the GCD of two numbers. The algorithm is based on the principle that the GCD of two numbers also divides their difference.

• Recursion: Each function uses recursion, calling itself with updated parameters until the base case (b == 0) is met.

Sample Input & Output:

Input:

• a = 48

• b = 18

Output: GCD of 48 and 18 is: 6

Conclusion:

Calculating the GCD is a common and essential task in programming. Understanding how to implement it in various languages enhances your algorithmic thinking and coding skills.

**  Please do subscribe my blog for future updates and share with your friends, if you find this informative **