Write a program to find GCD of two numbers

The Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two numbers is the largest number that divides both numbers exactly, without leaving any remainder. The formula used in Euclid’s Algorithm for finding the GCD is based on the idea that:

GCD(x, y) = x if y = 0
Otherwise, GCD(x, y) = GCD(y, x % y)

This means that you can keep reducing the problem by replacing the second number with the remainder of dividing the first number by the second. This continues until the second number becomes zero, at which point the first number is the GCD.

include <stdio.h>

// Function prototype declaration
int GCD(int x, int y);

void main() {
int a, b, gcd;

// Prompt the user to input two numbers
printf("Enter two numbers: ");
scanf("%d %d", &a, &b);

// Call the GCD function
gcd = GCD(a, b);

// Output the result
printf("GCD of %d and %d is %d", a, b, gcd);
}

// Recursive function to find GCD
int GCD(int x, int y) {
if (y == 0) // Base case: If the second number is 0, return the first number as GCD
return x;
else // Recursive step: Find GCD of y and remainder of x divided by y
return GCD(y, x % y);
}

Include the standard input/output library:
```
#include <stdio.h>
```
This line includes the stdio.h header file, which contains functions like printf and scanf for input and output.
Function declaration:
```
int GCD(int x, int y);
```
This line declares the prototype of the GCD function that will be defined later. The function takes two integers (x and y) as parameters and returns an integer (the GCD).
Main function:
```
void main() {
int a, b, gcd;
printf("Enter two numbers: ");
scanf("%d %d", &a, &b);
gcd = GCD(a, b);
printf("GCD of %d and %d is %d", a, b, gcd);
}
```
- int a, b, gcd; declares three integer variables: a (first number), b (second number), and gcd (to store the result).
- printf("Enter two numbers: "); prompts the user to enter two numbers.
- scanf("%d %d", &a, &b); reads the input numbers into variables a and b.
- gcd = GCD(a, b); calls the GCD function to compute the greatest common divisor of a and b, and stores the result in gcd.
- printf("GCD of %d and %d is %d", a, b, gcd); prints the result of the GCD calculation.
Recursive GCD function:
```
int GCD(int x, int y) {

if (y == 0)  // Base case: If the second number is 0, return the first number as GCD

return x;

else  // Recursive step: Find GCD of y and remainder of x divided by y

return GCD(y, x % y);

}
```
- The function GCD(int x, int y) uses recursion to calculate the GCD.
- Base case: If y == 0, it returns x because the GCD of any number and 0 is the number itself.
- Recursive case: If y is not zero, the function calls itself with y and the remainder of x divided by y (i.e., x % y). This reduces the size of the problem until y becomes 0.

Example Walkthrough:

Let’s walk through an example where the user inputs 21 and 35:

First call: GCD(21, 35)
- x = 21, y = 35
- Since y is not 0, we make the recursive call: GCD(35, 21 % 35) → GCD(35, 21)
Second call: GCD(35, 21)
- x = 35, y = 21
- Since y is not 0, we make the recursive call: GCD(21, 35 % 21) → GCD(21, 14)
Third call: GCD(21, 14)
- x = 21, y = 14
- Since y is not 0, we make the recursive call: GCD(14, 21 % 14) → GCD(14, 7)
Fourth call: GCD(14, 7)
- x = 14, y = 7
- Since y is not 0, we make the recursive call: GCD(7, 14 % 7) → GCD(7, 0)
Base case: GCD(7, 0)
- Since y == 0, we return x = 7.

Now, the function returns 7 all the way back through the recursion, and the final result is printed as:

GCD of 21 and 35 is 7

Example Output:

Enter two numbers: 21 35

GCD of 21 and 35 is 7

Points to Remember:

Recursion: The algorithm uses recursion to break down the problem. Each recursive call reduces the second argument until it becomes 0, at which point the GCD is found.
Modulo operation: The modulo operation (%) is key to finding the remainder when dividing x by y.