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.

Programming Tip: Healthy Iterations!

We, as programmers, often go on to write code that seems fine at the time of actually writing that chunk of code. But sometimes, we see that bit again to discover that we could actually optimize the code for better performance.

Below is some code which resembles something I wrote in PHP a while ago when working on one of my projects:

for ($i=0; $i<count($someArray); $i++) {
    print $someArray[$i];
}


At first glance, it might look like a nice & clean piece of code but a closer look is recommended. As you can see, the count($someArray) function is repeatedly called in all the iterations of the loop. This process puts a lot of stress on the PHP engine as compared to the alternative (and better) way. Whats the better way then you ask? Well, here it is:

$arrayLength = count($someArray);
for ($i=0; $i<$arrayLength; $i++) {
     print $someArray[$i];
}


As you can see, the function that counts the total number of elements in the array is called only once. That gives us a tremendous boost in the execution time. For a small site, this is not such a big issue I think. However, once you start getting more and more hits to your site, you should definitely look to optimize your code as much as possible.

Happy Coding!