GCD Algorithm
The GCD (Greatest Common Divisor) Algorithm, also known as the Euclidean Algorithm, is a widely-used mathematical method for finding the greatest common divisor of two integers. This divisor is the largest positive integer that evenly divides both numbers without leaving a remainder. The GCD Algorithm is important in number theory, simplifying fractions, and solving Diophantine equations, among other applications. It is an efficient technique for computing the GCD, as it relies on the fundamental properties of integers and the divisibility of numbers.
The GCD Algorithm works by repeatedly applying the modulo operation and replacing the given integers with the remainder until the remainder becomes zero. In its simplest form, the algorithm starts with two input numbers, a and b (with a ≥ b), and computes the remainder when a is divided by b. Then, it replaces a with b and b with the remainder, continuing this process until the remainder is zero. At this point, the greatest common divisor is the non-zero remainder obtained in the previous step. The efficiency of the GCD Algorithm arises from the fact that the numbers involved in the calculations rapidly decrease in size, resulting in fewer iterations and faster convergence to the solution.
#include <stdio.h>
// Euclid's algorithm
int GCD(int x, int y) {
if (y == 0)
return x;
return GCD(y, x%y);
}
int main() {
int a, b;
printf("Input two numbers:\n");
scanf("%d %d", &a, &b);
printf("Greatest common divisor: %d\n", GCD(a, b));
}
