Write a program in python to find gcd of two numbers.

GCD or HCF of two numbers is the largest number which divides both the numbers. For example, GCD of 12 and 16 is 4.

There are two methods to find gcd of two numbers, let’s see both of them.

Method 1: Using Loop

This method to find gcd using loop in python is a naive approach. Basically we first smaller of the two numbers, then we loop from smaller to 1 in decreasing order.

  1. Find smaller of the two numbers.
  2. Loop from smaller to 1 in decreasing order and check if its divides both the numbers.
  3. If yes then that number is the GCD.

Let’s see its implementation in Python.

Output

This method is not efficient for computing gcd. The second method which uses the Euclidean Algorithm is best for computing GCD.

Method 2: Using the Euclidean Algorithm

In this algorithm, we divide the larger number with the smaller and update the larger number to the smaller number and the smaller number to the remainder. We do this until we get the remainder as zero and the final value of the larger number will be the gcd.

Let’s see its implementation in Python code.

Output

In the above program l, s = s, l%s does the swapping/updation work. It update l to s and s to l%s.

If you have any doubts or suggestion then comment below.

Leave a Reply