GCD and LCM Calculation in Python
This program shows how to calculate the GCD and LCM of a pair of numbers. The source code is clear enough to be understood easily. The only thing that is required from you is some basic mathematics skills and a brain working normally.
print "GCD and LCM Calculator"
# the function to calculate the GCD
def gcd(num1, num2):
if num1 > num2:
for i in range(1,num2+1):
if num2 % i == 0:
if num1 % i == 0:
result = i
return result
elif num2 > num1:
for i in range(1,num1+1):
if num1 % i == 0:
if num2 % i == 0:
result = i
return result
else:
result = num1*num2/num1
return result
# the function to calculate the LCM
def lcm(num1, num2):
result = num1*num2/gcd(num1,num2)
return result
# ask what the user wants to calculate
print "Entar 'gcd' to calculate GCD"
print "Enter 'lcm' to calculate LCM"
choice = raw_input("Make your choice: ")
# get the input from the user
number1 = int(raw_input("Enter first number: "))
number2 = int(raw_input("Enter second number: "))
# now call the appropiate function depending on the user input
if choice == 'gcd':
print "The GCD is:", gcd(number1, number2)
elif choice == 'lcm':
print "The LCM is:", lcm(number1, number2)
else:
print "Wrong input"
This was an exercise given in ‘Core Python Programming‘ and I had a nice time doing it.
Hey,
Just thought you should know that your gcd function can be simplified quite a bit. This version will also run *much* faster. (hopefully the comment system won’t remove the whitespace).
def gcd(a,b):
while b > 0: a,b = b, a%b
return a
Regards,
Steve
Well the whitespace was removed, let me try again:
def gcd(a,b):
$nbsp;while b > 0: a,b = b, a%b
$nbsp;return a
If that still didn’t work, then just add a tab in front of the 2nd and 3rd lines in the function.
Crap… this is my last post, I promise :)
def gcd(a,b):
while b > 0: a,b = b, a%b
return a
thanks Steve! =)
make it Steve’s solution even shorter:
def gcd(a,b):
while b: a,b = b, a%b
return a