GCD using Euclidean algorithm in Python 3 Programming Language

PYTHON PROGRAM TO FIND OUT GCD USING EUCLIDEAN ALGORITHM 

WHAT IS EUCLIDEAN ALGORITHM

Hello Everyone today we will be taking out the GCD for the two numbers using the Euclidean algorithm as the title suggests 😆



Now for those of you who are thinking what Euclidean Algorithm is then:

Euclidean algorithm states that:

  1. The GCD of two numbers a and b if a is equal to one is b . Quite obvious right?
  2. The GCD of two numbers a and b if b is equal to one is a . Similar to the first one
  3.  If first 2 conditions are not satisfied then then the GCD = GCD of the quotient and remainder when the two numbers are divided.

NOTE: This is Only Valid if A is strictly greater than B

This is how the algorithm looks on paper: (source:Link to the website)



Now If you want to visually look at the algorithm then this website would be useful)

Link to the animation

WRITING THE EUCLIDEAN ALGORITHM IN PYTHON

Now that we know what Euclidean algorithm is lets get to the code:

So obviously after looking at the algorithm we can tell that it includes recursion

If you are not sure what recursion is then you can learn at :  learn recursion

So this is how the code would look in Python3


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def euclidean_rec(a,b):
	if a>b:                        # Checks the main condition that a>b 
		if a==1:                 # First Check  of Euclidean algorithm 

			return b                    
		elif b ==1:                       #Second Check of the algorithm
			return a
		else:
			return euclidean_rec(a//b,a%b)  #Recursion Call
	elif a == b:
		return a
	else:                                       #When B>A
		if a==1:
			return b
		elif b ==1:
			return a
		else:
			return euclidean_rec(b//a,b%a)
print(euclidean_rec(10,15))                             #Driver Function

Comments

Post a Comment