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; } }}

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 1, 2, 3, 4, 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.

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?

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

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…