Making the algorithm faster

Making it faster, one idea at a time.

1. Scan once, not twice. Check each j from 1 to max(m, n) against both numbers, instead of scanning m and n separately (m + n checks).

2. Stop at the smaller number. Collect common divisors directly, and stop at min(m, n): a common divisor can't be bigger than the smaller number.

3. Throw the list away. Keep only most-recent-common-divisor, starting at 1, and update it whenever a larger common divisor appears. At the end it is the gcd.

4. Use pairs. Divisors come in pairs (j, n/j), so checking j only up to √n finds them all. But then the list is no longer in increasing order, so 'rightmost' must become 'largest'.

5. Scan downwards. Start at min(m, n) and go down: the first common divisor you meet is the gcd, so you can stop at once.

Even so, these methods check about min(m, n) numbers: their work grows with the numbers' values, not with how many digits they have.