Back to algorithmsPodstawowy
Euclidean Algorithm (GCD)
The fastest way to get the GCD — the greatest common divisor of two numbers. Instead of checking every divisor, we replace the pair (a, b) with (b, a % b) until b is zero.
O(log min(a, b))O(1)OIJOILOGIA
🍰 Euclidean Algorithm — Games
Play both games to master the algorithm!
💡
Tip: Start with Game 1 — cutting the cake shows where a // b and a % b come from and why the last square is the GCD. In Game 2 you run the code yourself: you compute the remainders and keep track of the pair (a, b), exactly like on paper in a contest.