Euclidean GCD Algorithm in Python
The greatest common divisor is the largest positive integer that divides two integers without a remainder.
What is Euclidean GCD Algorithm?
The greatest common divisor is the largest positive integer that divides two integers without a remainder.
Find the greatest common divisor with Euclid's algorithm.
When should you use it?
- Practice problem solving and data structures.
- Process data when every algorithm step must be explicit.
- Prepare for programming exercises, exams, and interviews.
Example code
main.py
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))Expected output
6How it works
Each step replaces the pair with the smaller value and the remainder. When the remainder becomes zero, the remaining value is the GCD.
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.