The full form of GCD is ” Greatest Common Divisor”. Which means the greatest common factor of the two numbers. It is also known by the name HCF(Highest common factor). I will be using both the words so don’t confuse yourself.
I have used for loop, if-else statement, min() function and break statement.
We have checked both numbers by dividing them every number less than the minimum of both the numbers. And if that number divides both the numbers without leaving any remainder than that number becomes the HCF of the given numbers. And remember that I am running the loop in reverse order.
How to find gcd of two numbers
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | # taking first number num1 = int(input("Enter first number: ")) # taking second number num2 = int(input("Enter second number: ")) gcd = 1 # finding GCD for i in range(min(num1,num2),0,-1): if (num1%i) == 0 and (num2%i) == 0: gcd = i break # printing GCD print("The GCD of the two numbers is ", gcd) |
Output:
1 2 3 4 5 | Enter first number: 28 Enter second number: 63 The GCD of the two numbers is 7 |
Finding GCD or HCF of two numbers using Euclid’s algorithm in python
In this method, we are going to use Euclid’s algorithm which is much faster. I have used while loop, if-else statement, and swapping technique.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | # taking first number num1 = int(input("Enter first number: ")) # taking second number num2 = int(input("Enter second number: ")) # checking if num2 is greater than num1 then swap these numbers if num2 > num1: (num1,num2) = (num2,num1) # repeat these steps till num2 divides num1 with remainder zero while num1%num2 != 0: # swap num1 to num2 and num2 with remainder (num1,num2) = (num2,num1%num2) # printing GCD print("The GCD of the numbers is ",num2) |
Output:
1 2 3 4 5 | Enter first number: 28 Enter second number: 63 The GCD of the numbers is 7 |
Finding GCD or HCF of two numbers by Euclid’s algorithm using recursion in python
Here we have made a recursive function gcd().
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | # defining gcd function def gcd(num1,num2): if num1%num2 == 0: # Base case return num2 else: # Iterative case return gcd(num2,num1%num2) # taking first number num1 = int(input("Enter first number: ")) # taking second number num2 = int(input("Enter second number: ")) # checking if num2 is greater than num1 then swap these numbers if num2 > num1: (num1,num2) = (num2,num1) # printing GCD print("The GCD of the numbers is",gcd(num1,num2)) |
Output:
1 2 3 4 5 | Enter first number: 28 Enter second number: 63 The GCD of the numbers is 7 |
In this program, we used many things which I used to make previous programs and also learnt about many other things about python.
Now you can try some other programs. And If you find any problem then you can always contact me or comment below.
