1. GCD - Euclid’s Algorithm #

Created Tuesday 28 July 2020

GCD(Greatest Common Divisor) - aka HCF(Highest Common Factor) - Name is enough for description.

Naive algorithm:

// if a==0 or b==0, gcd = min(a, b)

gcd(a, b):
	gcd_val = 1;
	small = min(a, b);// smaller of the two, can potentially be the max gcd
	for(int i=1; i<small; i++)
		if(a%i==0m && b%i==0)
			gcd_val = i;
	return gcd_val

O(n) approach, very slow.

Euclid’s Algorithm:

• It is an ancient, yet efficient algorithm to find GCD of two numbers.

Algorithm(Statement):

gcd(a, b) = gcd(b, a%b); // b is the smaller one
gcd(0, n) = x; // base case

Proof by observation.

Divisor property: gcd(a,b) = gcd(a-b, b); // holds primarily