Python Program for Basic Euclidean algorithms

Created with Sketch.
Python Programming Examples

Python Program for Basic Euclidean algorithms

# Python program to demonstrate Basic Euclidean Algorithm
 
 
# Function to return gcd of a and b
def gcd(a, b): 
    if a == 0 :
        return b 
     
    return gcd(b%a, a)
 
a = 10
b = 15
print("gcd(", a , "," , b, ") = ", gcd(a, b))
 
a = 35
b = 10
print("gcd(", a , "," , b, ") = ", gcd(a, b))
 
a = 31
b = 2
print("gcd(", a , "," , b, ") = ", gcd(a, b))
 
# 
chevron_right

filter_none
Output: 
GCD(10, 15) = 5
GCD(35, 10) = 5
GCD(31, 2) = 1
Time Complexity: O(Log min(a, b))
 0
 
Leave a Reply 
Your email address will not be published. Required fields are marked *
 
 
 
  
©  2024 python tutorials.  python-tutorials.in