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.
- Find smaller of the two numbers.
- Loop from smaller to 1 in decreasing order and check if its divides both the numbers.
- If yes then that number is the GCD.
Let’s see its implementation in Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | print("Enter two numbers") a = int(input()) b = int(input()) smaller = 0 #find smaller number if a < b: smaller = a else: smaller = b #find the highest factor of a and b for i in range(smaller, 0,-1): if (a%i == 0) and (b%i == 0): print("GCD: ",i) break |
Output
1 2 3 4 | Enter two numbers 12 16 GCD: 4 |
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.
1 2 3 4 5 6 7 8 9 10 | def findGCD(l, s): while(s): l, s = s, l%s return l print("Enter two numbers") a = int(input()) b = int(input()) print("GCD: ",findGCD(a,b)) |
Output
1 2 3 4 | Enter two numbers 50 10 GCD: 10 |
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.