Greatest Common Divisor
Euclid's method repeatedly replaces a pair with the divisor and remainder.
What is Greatest Common Divisor?
Euclid's method repeatedly replaces a pair with the divisor and remainder.
Find the greatest common divisor of two integers.
Important points
- Compile with warnings enabled and fix every warning.
- Know the lifetime and type of every value.
- Validate input and keep array bounds explicit.
C and C++ code examples
main.c
#include <stdio.h>
int main(void) {
int left = 48, right = 18;
// Reduce the pair until no remainder remains.
while (right) { int remainder = left % right; left = right; right = remainder; }
printf("gcd=%d\n", left);
}
gcd=6C++
main.cpp
#include <iostream>
#include <numeric>
int main() {
// std::gcd implements Euclid's algorithm.
std::cout << "gcd=" << std::gcd(48, 18) << '\n';
}
gcd=6C and C++ comparison
When the remainder reaches zero, the current divisor is the greatest common divisor.
C
C exposes small procedural APIs and makes representation details explicit.
C++
C++ retains the low-level model while adding safer library types and abstractions.
Practice exercises
Run both versions, then modify them to observe the different language guarantees.
- Add invalid and boundary-value inputs.
- Compile with -Wall -Wextra -Wpedantic.
- Move reusable declarations into a header and implementation file.