How do you find the hcf and gcd of two numbers in python?
In this example, you will learn to find the GCD of two numbers using two different methods: function and loops and, Euclidean algorithm Show
To understand this example, you should have the knowledge of the following Python programming topics:
The highest common factor (H.C.F) or greatest common divisor (G.C.D) of two numbers is the largest positive integer that perfectly divides the two given numbers. For example, the H.C.F of 12 and 14 is 2. Source Code: Using Loops
Output The H.C.F. is 6 Here, two integers stored in variables num1 and num2 are passed to the In the function, we first determine the smaller of the two numbers since the H.C.F can only be less than or equal to the smallest number. We then use a In each iteration, we check if our number perfectly divides both the input numbers. If so, we store the number as H.C.F. At the completion of the loop, we end up with the largest number that perfectly divides both the numbers. The above method is easy to understand and implement but not efficient. A much more efficient method to find the H.C.F. is the Euclidean algorithm. Euclidean algorithmThis algorithm is based on the fact that H.C.F. of two numbers divides their difference as well. In this algorithm, we divide the greater by smaller and take the remainder. Now, divide the smaller by this remainder. Repeat until the remainder is 0. For example, if we want to find the H.C.F. of 54 and 24, we divide 54 by 24. The remainder is 6. Now, we divide 24 by 6 and the remainder is 0. Hence, 6 is the required H.C.F. Source Code: Using the Euclidean Algorithm
Here we loop until y becomes zero. The statement In each iteration, we place the value of y in x and the remainder Here, in this section we will discuss how to find HCF of two numbers in python. HCF means (Highest Common Factor) also known as GCD (Greatest Common Divisor). x is called HCF of a & b two conditions :
What's on the Page
Method 1 : Linear QuestAlgorithm
Method 1 : Python CodeRun num1 = 36 num2 = 60 hcf = 1 for i in range(1, min(num1, num2)): if num1 % i == 0 and num2 % i == 0: hcf = i print("Hcf of", num1, "and", num2, "is", hcf) OutputMethod 2 : Repeated Subtraction
Algorithm
Method 2 : Python CodeRun num1 = 36 num2 = 60 a = num1 b = num2 while num1 != num2: if num1 > num2: num1 -= num2 else: num2 -= num1 print("Hcf of", a, "and", b, "is", num1) OutputMethod 3 : Repeated Subtraction using RecursionAlgorithm
Method 3 : Python CodeRun # Recursive function to return HCF of two number def findHCF(num1, num2): # Everything divides 0 if num1 == 0 or num2 == 0: return num1 + num2 # base case if num1 == num2: return num1 # num1>num2 if num1 > num2: return findHCF(num1 - num2, num2) else: return findHCF(num1, num2 - num1) num1 = 36 num2 = 60 print("Hcf of", num1, "and", num2, "is", findHCF(num1, num2)) OutputMethod 4 : Repeated Subtraction with Modulo Operator using RecursionAlgorithm
Method 4 : Python CodeRun # This method improves complexity of repeated subtraction # By efficient use of modulo operator in euclidean algorithm def getHCF(a, b): return b == 0 and a or getHCF(b, a % b) num1 = 36 num2 = 60 print("Hcf of", num1, "and", num2, "is", getHCF(num1, num2)) ‘ Output
Method 5 : Handling Negative Numbers in HCFAlgorithmIf any of the number is negative then convert it to positive by multiplying it with -1 as according to the proper definition HCF of two numbers can never be negative.
Method 5 : Python CodeRun # This method improves complexity of repeated subtraction # By efficient use of modulo operator in euclidean algorithm def getHCF(a, b): return b == 0 and a or getHCF(b, a % b) num1 = -36 num2 = 60 # if user enters negative number, we just changing it to positive # By definition HCF is the highest positive number that divides both numbers # -36 & 60 : HCF = 12 (as highest num that divides both) # -36 & -60 : HCF = 12 (as highest num that divides both) num1 >= 0 and num1 or -num1 num2 >= 0 and num2 or -num2 print("Hcf of", num1, "and", num2, "is", getHCF(num1, num2)) Output
How do you find HCF of two numbers in Python?num1 = int(input("Enter first number: ")) num2 = int(input("Enter second number: ")) # printing the result for the users. print("The H.C.F. of", num1,"and", num2,"is", calculate_hcf(num1, num2))
How do you find the HCF and gcd of two numbers?First, divide the large number by a small number. If the remainder is left, then divide the first divisor by remainder. If the remainder divides the first divisor completely, then it is the HCF or highest common factor of the given two numbers.
How do I get gcd in Python?gcd() method returns the greatest common divisor of the two integers int1 and int2. GCD is the largest common divisor that divides the numbers without a remainder. GCD is also known as the highest common factor (HCF). Tip: gcd(0,0) returns 0.
How do you find the HCF and LCM of two numbers in Python?Algorithm. Initialize HCF = 1.. Run a loop in the iteration of (i) between [1, min(num1, num2)]. Note down the highest number that divides both num1 & num2.. If i satisfies (num1 % i == 0 && num2 % i == 0) then new value of HCF is i.. Use lcm formula :- (num1*num2) / hcf.. Print the output.. |