WAP (Python) to find the HCF/GCD of two numbers

Hey all, in this amazing tutorial, we are going to find the HCF (Highest Common Factor) or GCD (Greatest Common Divisor) of two numbers in Python. So open your code editors, as we are going to do this problem in the best way possible!

You can find the final code of this problem at the end of this article. But, I would suggest you to be with us this whole journey as we are going to go through each and every step you need to follow to become the best coder in the world!!!

Also read: WAP (Python) to check if a string/number is a palindrome or not

What is HCF/GCD?

In simple terms, the HCF (Highest Common Factor) of two numbers is the biggest number that divides both the numbers. 

For example: To find the HCF of 8 and 12:

Writing factors of 8: 1, 2, 4, 8

Writing factors of 12: 1, 2, 3, 4, 6, 12

It can be clearly seen that the highest common number that divides both 8 and 12 is 4. Hence, 4 is their HCF!

I hope that you now understand the meaning of HCF. Now, let's put this knowledge into code!

Overview:

In this problem, we are asked to find the HCF/GCD of two numbers in Python. Although there is one method that I told you earlier, but that method is not feasible for solving this problem, hence we would use a different method for that. 

*Note- If you have read our previous article, where we found the LCM of two numbers, then you can also find the HCF of those two numbers by just using the formula: 

LCM x HCF = num1 x num2 

This is just another way to solve this problem. Just try it out!*

Read the previous article here: WAP (Python) to find the LCM of two numbers

It is a known fact that the HCF of two numbers cannot be more than the smaller number, hence we would write a loop that would divide both the main numbers with every number starting from 1 till the smallest number. The last number to divide both the main numbers simultaneously will be our HCF!

*As I have already told you the working of this program, you can try to write it on your own.*

Understanding what we need to do:

Here I will tell you step by step what you need to do.

Step 1: Taking the input from the user:

This is the easiest part. Here we would just ask the user to enter the first number (num1) and then the second number (num2). Also, don't forget to typecast this input into integer by using the 'int' command, as we have to do calculations on it.

Here's the code for this step:

Step 2: Finding the HCF of two numbers:

Now, as I said in the Overview, the HCF of two numbers can't be greater than the smallest number. Hence, we need to find the smallest number among num1 and num2. We will do that using the 'min' function. I have stored this value in a variable called 'mn'. 

Next, we need to check divisibility of both the numbers with every number from 1 till 'mn'. Hence we would put the range in the 'for' function to be from 1 till 'mn +1' as the loop ends at one less than the final limit. We have taken the variable to be iterated as 'i'.

Now, we would check if both the numbers are divisible by 'i', if it is then, we would assign the value of another variable 'hcf' to be equal to 'i'. The loop will iterate until it reaches 'mn'. And thus the largest number that fulfills the condition becomes our HCF! 

Here's the code for this step:

*Note that we have used the 'and' keyword to signify that the 'if' statement runs only when both the conditions satisfies.*

So, there it is! We have found the best way to WAP (Python) to find the HCF of two numbers!

Here's the final code:

And here ends our amazing tutorial where you learnt the best method to find the HCF of two numbers in Python! I hope you liked it, and if you did, then don't forget to share it to others. This can really help someone struggling in this problem.

Also, please subscribe to our newsletter as we do these coding sessions regularly!

Again, thanks for reading!!!