w3resource

Python Math: Implement Euclidean Algorithm to compute the greatest common divisor

Python Math: Exercise-76 with Solution

Write a Python program to implement Euclidean Algorithm to compute the greatest common divisor (gcd).

Note: In mathematics, the Euclidean algorithm[a], or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 147 = 252 − 105.

Sample Solution:-

Python Code:

from math import *

def euclid_algo(x, y, verbose=True):
	if x < y: # We want x >= y
		return euclid_algo(y, x, verbose)
	print()
	while y != 0:
		if verbose: print('%s = %s * %s + %s' % (x, floor(x/y), y, x % y))
		(x, y) = (y, x % y)
	
	if verbose: print('gcd is %s' % x) 
	return x


euclid_algo(150, 304)
euclid_algo(1000, 10)
euclid_algo(150, 9)

Sample Output:

304 = 2 * 150 + 4                                                                                             
150 = 37 * 4 + 2                                                                                              
4 = 2 * 2 + 0                                                                                                 
gcd is 2                                                                                                      
                                                                                                              
1000 = 100 * 10 + 0                                                                                           
gcd is 10                                                                                                     
                                                                                                              
150 = 16 * 9 + 6                                                                                              
9 = 1 * 6 + 3                                                                                                 
6 = 2 * 3 + 0                                                                                                 
gcd is 3

Pictorial Presentation:

Python Math: Implement Euclidean Algorithm to compute the greatest common divisor

Flowchart:

Flowchart: Implement Euclidean Algorithm to compute the greatest common divisor

Visualize Python code execution:

The following tool visualize what the computer is doing step-by-step as it executes the said program:

Python Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a Python program to calculate clusters using Hierarchical Clustering method.
Next: Write a Python program to convert RGB color to HSV color.

What is the difficulty level of this exercise?

Test your Python skills with w3resource's quiz



Python: Tips of the Day

What does if __name__ == "__main__": do?

Whenever the Python interpreter reads a source file, it does two things:

  • it sets a few special variables like __name__, and then
  • it executes all of the code found in the file.

Let's see how this works and how it relates to your question about the __name__ checks we always see in Python scripts.

Code Sample

Let's use a slightly different code sample to explore how imports and scripts work. Suppose the following is in a file called foo.py.

Example:

# Suppose this is foo.py.

print("before import")
import math

print("before functionA")
def functionA():
    print("Function A")

print("before functionB")
def functionB():
    print("Function B {}".format(math.sqrt(100)))

print("before __name__ guard")
if __name__ == '__main__':
    functionA()
    functionB()
print("after __name__ guard")

Special Variables

When the Python interpeter reads a source file, it first defines a few special variables. In this case, we care about the __name__ variable.

When Your Module Is the Main Program

If you are running your module (the source file) as the main program, e.g.

Example:

python foo.py

the interpreter will assign the hard-coded string "__main__" to the __name__ variable, i.e.

# It's as if the interpreter inserts this at the top
# of your module when run as the main program.
__name__ = "__main__"

When Your Module Is Imported By Another

On the other hand, suppose some other module is the main program and it imports your module. This means there's a statement like this in the main program, or in some other module the main program imports:

# Suppose this is in some other main program.
import foo

The interpreter will search for your foo.py file (along with searching for a few other variants), and prior to executing that module, it will assign the name "foo" from the import statement to the __name__ variable, i.e.

# It's as if the interpreter inserts this at the top
# of your module when it's imported from another module.
__name__ = "foo"

Executing the Module's Code

After the special variables are set up, the interpreter executes all the code in the module, one statement at a time. You may want to open another window on the side with the code sample so you can follow along with this explanation.

Always

  1. It prints the string "before import" (without quotes).
  2. It loads the math module and assigns it to a variable called math. This is equivalent to replacing import math with the following (note that __import__ is a low-level function in Python that takes a string and triggers the actual import):
    3. # Find and load a module given its string name, "math",
# then assign it to a local variable called math.
math = __import__("math")
  3. It prints the string "before functionA".
  4. It executes the def block, creating a function object, then assigning that function object to a variable called functionA.
  5. It prints the string "before functionB".
  6. It executes the second def block, creating another function object, then assigning it to a variable called functionB.
  7. It prints the string "before __name__ guard".

    8. Only When Your Module Is the Main Program

  8. If your module is the main program, then it will see that __name__ was indeed set to "__main__" and it calls the two functions, printing the strings "Function A" and "Function B 10.0".

    9. Only When Your Module Is Imported by Another

  9. (instead) If your module is not the main program but was imported by another one, then __name__ will be "foo", not "__main__", and it'll skip the body of the if statement.

    10. Always

  10. It will print the string "after __name__ guard" in both situations.

Summary

In summary, here's what'd be printed in the two cases:

# What gets printed if foo is the main program
before import
before functionA
before functionB
before __name__ guard
Function A
Function B 10.0
after __name__ guard

# What gets printed if foo is imported as a regular module
before import
before functionA
before functionB
before __name__ guard
after __name__ guard

Ref: https://bit.ly/2YeDXKc