Skip to content
Econowmics
Menu
  • Home
  • Economics
    • Econometrics
    • Economics and History
    • Macroeconomics
    • Microeconomics
    • Miscellaneous
      • Awards and Honors
      • Economic Schools of Thought
      • Economic Quotes
      • Economic Videos
    • Terms and Concepts
  • Cognitive Biases
  • Data Analysis
    • Statistics
    • Python Programming
  • Contact
Menu
[Python] Greatest Common Factor

[Python] Greatest Common Factor

Posted on

 

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

 

 

[Python] Greatest Common Factor
Photo by Pixabay from Pexels

 

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:

X Y |X-Y|
63 28 35
35 28 7
7 28 21
7 21 14
7 14 7
7 7 0

 

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:

Greatest Common Factor Function in Python

 

 

 

 

Related posts:

[Python] Catalan Numbers
[Python] Pandigital numbers
[Python] Prime number generator
Shakespeare's Nightmare: Monkeys on Typewriters
[Python] Palindrome Checking Function

Anything in here will be replaced on browsers that support the canvas element

  • Amos Tversky
  • Daniel Kahneman
  • cognitive bias
  • Milton Friedman
  • Wealth of Nations
  • Nobel Prize Laureate
  • Adam Smith
  • 20:20 ratio
  • law of small numbers
  • the halo effect
  • wealth inequality
  • income inequality
  • Law of Large Numbers
  • Dow Jones Industrial Average
  • status quo bias
  • Behavioral Economics
  • daniel kahnemann
  • hyperinflation
  • the gambler's fallacy
  • gambler's fallacy
©2023 Econowmics | Design: Newspaperly WordPress Theme