Introduction
Given two non-negative integers and , we want to find their greatest common divisor (GCD), that is, the largest positive integer that divides both numbers.
For example:
Given two non-negative integers and , we want to find their greatest common divisor (GCD), that is, the largest positive integer that divides both numbers.
For example:
Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:
Formally,
Here, the symbol means divisibility. For example, means that divides .
The Euclidean algorithm is based on several simple observations.
If one of the numbers is zero, then the GCD is the other number.
The order of the numbers does not matter.
Assume . Then:
Indeed, subtracting from does not change the common divisors.
If we repeat this subtraction many times, we eventually get the remainder of dividing by . So a faster version is:
Using this idea, we get the main recursive formula:
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int gcd(int a, int b) {
while (b != 0) {
a %= b;
swap(a, b);
}
return a;
}