Hey guys, in this blog we will see a Python Program to Find HCF or GCD.
Example 1: Using Loops
# Python Program to Find HCF or GCD # define hcf function def compute_hcf(x, y): # choose the smaller number if x > y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = int(input('Enter 1st number -> ')) num2 = int(input('Enter 2nd number -> ')) print("The H.C.F. is", compute_hcf(num1, num2))
Enter 1st number -> 24 Enter 2nd number -> 24 The H.C.F. is 24
Enter 1st number -> 34 Enter 2nd number -> 24 The H.C.F. is 2
Enter 1st number -> 50 Enter 2nd number -> 100 The H.C.F. is 50
- Suppose we enter two numbers 12 and 24.
- It will traverse from 1 to 13 (12+1) and check with every number that both 12 and 24 are divisible by that number or not.
- If it is divisible, it will be the current HCF.
- The HCF for 12 and 24 will be 12 itself.
Example 2: Using Euclidean Algorithm
# Python Program to Find HCF or GCD Using Euclidean algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(int(input("1st number -> ")), int(input("2nd number -> "))) print("The HCF is", hcf)
1st number -> 12 2nd number -> 4 The HCF is 4
1st number -> 23 2nd number -> 32 The HCF is 1
1st number -> 8884 2nd number -> 4448 The HCF is 4
Following is the Euclidean Algorithm to calculate the HCF of a number:
while(y): x, y = y, x % y return x
Check out our other python programming examples…