find 2 largest equal numbers

[deanhystad]

Though short my solution is far from efficient. Given my two numbers 42 and 154 I know for sure that there will not be any common denominators in the range 22 to 41 or the range 15 to 20 or... My quick and dirty works fine if one of the numbers if fairly small, but there is a lot of needless division going on and this could result in long delays if both of your numbers are large.

Division is costly, so if you can do fewer divisions your algorithm is going to run faster. The 30 line GCD program you mention is probably using Stein's algorithm. Steins algorithm replaces division with shifts and subtraction. This requires a lot of testing to determine the next step in the algorithm, but you can do a lot of if statements in the time it takes to do 1 division.

Or maybe you saw Euclid's algorithm. Euclid's algorithm still does division, but is more efficient because it does less of it. But I don't think I've ever seen an implementation of Euclid's algorithm that is 30 lines long. Normally the code is pretty short.

def gcd(a, b):
  if b == 0:
    return a:
  else:
    return gcd(b, (a % b))

Or even shorter

def gcd(a, b):
    return a if b == 0 else gcd(b, (a % b))

Though this does less division than my example it does use recursion, so some of the performance gains are lost. It also doesn't generate a list or common denominators, just the greatest common denominator.