<

Finding GCD (Euclidean Algorithm)

Published on
3,852 Points
852 Views
Last Modified:
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20.

The divisors of 12 are 1, 2, 3, 4, 6, 12
The divisors of 20 are 1, 2, 4, 5, 10 20

The highest number among the common divisors of 12 and 20 is 4. The gcd of 12 and 20 is 4. We'll start finding our answer by taking minimum of 12 and 20 which is 12. We'll return the highest number between 12 and 1 which is divided by 12 and 20. The steps are given below:

Is 12 divided by 12 and 20? No, decrement 12 by 1 which is 11
Is 11 divided by 12 and 20? No, decrement 11 by 1 which is 10
Is 10 divided by 12 and 20? No, decrement 10 by 1 which is 9
......................................................................................................
......................................................................................................
Is 5 divided by 12 and 20? No, decrement 5 by 1 which is 4
Is 4 divided by 12 and 20? Yes, we return 4 as our answer.

The implementation of the above algorithm is -
 
public int gcd(int a, int b) {
	for(int div = minimum(a, b); div >= 1; --div) {
		if(a % div == 0 && b % div == 0) {
			return div;
		}
	}
}

Open in new window

Let's consider two other numbers 540 and 600 and find their gcd. 
 
The divisors of 540 are 1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 27, 30, 36, 45, 54, 60, 90, 108, 135, 180, 270, 540
The divisors of 600 are 1234, 5, 6, 8, 10, 12, 15, 20, 24 25, 30, 40, 50, 60, 75, 100, 120, 150, 200, 300, 600

The above algorithm is not optimal for this example because it performs many comparisons (starting from 540, decrementing by 1 for each iteration down to 60) to find the actual solution. So, the iteration keeps going (540, 539, 538, .........., 60) until we get 60.

There is another approach given below which is known as Euclidean algorithm. In this approach, we consider (600, 540) as a pair and divide the larger number by smaller one. This forms a new pair (540, 60) where 540 is the smaller number of previous pair and 60 is the difference between previous pair. This process repeats until one value of the pair becomes 0. This approach is faster and more efficient than the previous approach. 

 
540 | 600 | 1
      540
-----------------
      60  | 540 | 9
            540
------------------
             X

That is, gcd(600, 540) = gcd(540, 600 mod 540)
                       = gcd(540, 540 mod 60)
                       = gcd(60, 0)
                       = 60

Open in new window

Euclidean algorithm is


public int gcdEucledian(int a, int b) {
	while(b > 0) {
		int temp = a % b;
		a = b;
		b = temp;
	}
}

Open in new window


Please keep in mind that efficiency of algorithm really matters when we consider a very big number. The first approach will take forever to find the gcd of a pair that has a long long integer equal to or greater than 9,223,372,036,854,775,803. As a user would you ever use a calculator that takes 30 seconds or more to calculate gcd?

0
Comment
0 Comments

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Join & Write a Comment

This video shows how to quickly and easily deploy an email signature for all users in Office 365 and prevent it from being added to replies and forwards. (the resulting signature is applied on the server level in Exchange Online) The email signat…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month