[Python] Greatest Common Factor

While many theories were put forth, there was one common factor that researchers recognized in all great performers: they practiced so hard and intensely that it hurt.

Sean Patrick, Nikola Tesla: Imagination and the Man That Invented the 20th Century

The Greatest Common Factor or GCF (also called Highest Common Factor or Greatest Common Divisor) of two numbers is simply the largest integer that divides both numbers evenly, i.e., without any remainders.

For instance, consider the two numbers 28 and 63. To calculate their GCF, we can first list their factors:

Factors of 28 are 1, 2, 4, 7, 14 and 28.

Factors of 63 are 1, 3, 7, 9, 21 and 63.

As is evident, the common factors of the two numbers are 1 and 7. Hence, their greatest common factor is 7.

Now consider the two numbers 24 and 36. Listing their factors we have:

Factors of 24 are 1, 2, 3, 4, 6, 8, 12, 24

Factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18, 36

We can see that their common factors are 1, 2, 3, 4, 6 and 12. Therefore, their GCF is 12.

Euclidean Algorithm to find the GCF of two numbers

First, let us bear in mind that the GCF of two numbers also divides their difference. For example, as calculated above, the GCF of 28 and 63 is 7, and it also divides their difference, 63-28 = 35.

Also, keep in mind that the GCF of a number and itself is always that same number, or GCF (x, x) = x

Therefore, we can set up an algorithm to find the GCF as follows:

• Take two given integers x and y
• Replace the larger one with the difference of the two
• Continue this process until the difference is equal to zero (i.e. the two numbers are the same)
• GCD is the value of x or y in the last step

So, to find the GCD of 28 and 63 we follow these steps:

Let’s jump to the code:

[pastacode lang=”python” manual=”%22%22%22%20Econowmics.com%20%22%22%22%0A%0A%0A%23%20Function%20to%20find%20GCF%20the%20Using%20Euclidian%20algorithm%0Adef%20GCF(x%2C%20y)%3A%0A%20%20%20%20%23Use%20the%20Euclidean%20Algorithm%20until%20y%20equals%20zero%0A%20%20%20%20while%20y%20%3E%200%3A%0A%20%20%20%20%20%20%20%20x%2C%20y%20%3D%20y%2C%20abs(x%20-%20y)%0A%20%20%20%20return%20x” message=”” highlight=”” provider=”manual”/]

Testing for the cases considered above we get: