Advanced - 1

Advanced Section - 1

Contents:

1. GCD of numbers

Euclidean algorithm for GCD (Basic)

GCD of two numbers is the largest number that divides both of them. A simple way to
find GCD is to factorize both numbers and multiply common factors.

Basic Euclidean Algorithm for GCD

The algorithm is based on below facts.

• If we subtract smaller number from larger (we reduce larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
• Now instead of subtraction, if we divide smaller number, the algorithm stops when we find remainder 0.

.

Below is a recursive function to evaluate gcd using Euclid’s algorithm.

int gcd(int a, int b)

{Ki

   if (a == 0) return b;

   return gcd(b % a, a);

}

GCD(10, 15) = 5

GCD(35, 10) = 5

GCD(31, 2) = 1

Time Complexity: O(Log min(a, b))