What's an intuitive way to understand how this algorithm finds the GCD?
function gcd(a, b) {
while (a != b)
if (a, b)
a -= b;
else
b -= a;
return a;
}
Wikipedia has a good article on it under the name Euclidean algorithm. In particular, this image from the article might answer your literal question: the intuitive way to understand how this algorithm finds GCD:
Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions a = 1071 and b = 462. Squares of size 462×462 are placed within it leaving a 462×147 rectangle. This rectangle is tiled with 147×147 squares until a 21×147 rectangle is left, which in turn is tiled with 21×21 squares, leaving no uncovered area. The smallest square size, 21, is the GCD of 1071 and 462.