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)
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 likeprintf
andscanf
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
andy
) 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), andgcd
(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 variablesa
andb
.gcd = GCD(a, b);
calls theGCD
function to compute the greatest common divisor ofa
andb
, and stores the result ingcd
.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 returnsx
because the GCD of any number and 0 is the number itself. - Recursive case: If
y
is not zero, the function calls itself withy
and the remainder ofx
divided byy
(i.e.,x % y
). This reduces the size of the problem untily
becomes 0.
- The function
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 returnx = 7
.
- Since
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 dividingx
byy
.