Solution: Greatest Common Divisor

Solutions for the Greatest Common Divisor Problem.

Naive solution

Here is the simplest, but terribly slow, way to compute the greatest common divisor:


 GCD(a,b)GCD(a,b)
 for d from min(a,b)(a,b) downto 1:
  if d divides both a and b:
   return d


For example, for a=109= 10^9 and b=109+1= 10^9 + 1, this algorithm will perform about 10910^9 divisions.

Stop and think: If you computed GCD(GCD(a,, b)), could you immediately find GCD(GCD(a-b,, b))?

A simple, but crucial idea, that will lead us to a much faster algorithm is suggested by the illustration below.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.