In this tutorial, we will learn how to find HCF (Highest Common Factor) using Python Programming. But before moving to the topic let's understand briefly about HCF / GCD.
HCF (Highest Common Factor).
The Highest Common Factor (HCF) is also known as the Greatest Common Divisor (GCD). It represents the largest positive integer that divides each of the numbers without leaving a remainder.
The Euclidean Algorithm is an ancient and efficient method for finding the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two numbers. The algorithm is based on the fact that the HCF of two numbers remains the same even if the larger number is replaced by the remainder when divided by the smaller number.
Example: Find HCF of 48 and 18.
Solution: 1. Take-Two Numbers: a = 48, b = 18 2. Divide the Larger Number by the Smaller Number: a/b = 48/18 = 2 with a remainder of r=12. 3. Replace Larger Number with Smaller Number and Remainder: Replace a with b and b with r so, a = 18, b = 12 4. Repeat the process: a/b = 18/12 = 1 with a remainder of r = 6. 5. Replace again: Replace a with b and b with r so, a = 12, b = 6 6. Continue Until Remainder is Zero: Repeat the process until the remainder becomes zero. a/b = 12/6 = 2 with a remainder of r = 0. 7. The Last Non-Zero Remainder is the HCF:
The last non-zero remainder is the HCF.The last non-zero remainder is 6, so HCF of 48 and 18 is 6.
Python Code for Finding HCF.
Here's a Python program that uses the Euclidean Algorithm to find the HCF of two numbers:
# Python code to find HCF of two numbers def find_hcf(a, b): while b: a, b = b, a % b return a # Example usage: num1 = 64 num2 = 22 hcf_result = find_hcf(num1, num2) print(f"The HCF of {num1} and {num2} is {hcf_result}")
The HCF of 64 and 22 is 2
Explanation:
In the above example, the find_hcf function takes two numbers, a and b, as parameters. It uses a while loop to repeatedly set a to the value of b, and b to the remainder when a is divided by b. This process continues until b becomes zero, and the last non-zero remainder is the HCF.
No comments:
Post a Comment