**Greatest common factor python: **Have you mastered basic programming topics of java and looking forward to mastering advanced topics in a java programming language? Go with these ultimate Advanced java programs examples with output & achieve your goal in improving java coding skills.

**Highest Common Factor (HCF) / Greatest Common Divisor (GCD) :**

**How to find gcd in python: **When at least one of the integers is not zero, the greatest positive integer that evenly divides the numbers without a remainder is called the Highest Common Factor or Greatest Common Divisor.

The GCD of 12 and 16 is, for example, 4.

Given two numbers the task is to find the highest common factor of the two numbers in Python.

- Java Program to Find HCF of Two Numbers Using Recursion
- C Program to Find GCD or HCF of Two Numbers using For Loop
- C Program to Find Hcf and Lcm of Two Numbers

**Examples:**

**Example1:**

**Input:**

a= 24 b=36

**Output:**

The Highest Common Factor (HCF) of the numbers 24 36 = 12

**Example2:**

**Input:**

a= 18 b=72

**Output:**

The Highest Common Factor (HCF) of the numbers 18 72 = 18

**Example3:**

**Input:**

a= 4 b=8

**Output:**

The Highest Common Factor (HCF) of the numbers 4 8 = 4

**Example4:**

**Input:**

a= 9 b=9

**Output:**

The Highest Common Factor (HCF) of the numbers 9 9 = 9

**Explanation:**

The Highest common factor of two numbers is number itself if both the numbers are equal

## Python Program to Calculate the HCF/GCD

**Python greatest common divisor: **There are several ways to calculate the hcf of the two numbers in python some of them are:

Explore more instances related to python concepts from Python Programming Examples Guide and get promoted from beginner to professional programmer level in Python Programming Language.

### Method #1:Using loops

**Below is the implementation:**

# function which computes and returns the highest common factor of the given two numbers def findGcd(number1, number2): # finding the smaller number if number1 > number2: smallNumber = number2 else: smallNumber = number1 # using for loop to traverse from 1 to smaller number for i in range(1, smallNumber+1): # if it divides the given two numbers without leaving the # remainder then assign result it with that loop iterator value if((number1 % i == 0) and (number2 % i == 0)): result = i # return the final result which is greatest common divisor(GCD) return result # given two numbers # given number a number1 = 24 # given number b number2 = 36 # passing the given two numbers to findGcd function which returns the greatest common factor of the given two numbers ans = findGcd(number1, number2) # print the hcf of the given two numbers print("The Highest Common Factor (HCF) of the numbers", number1, number2, "=", ans)

**Output:**

The Highest Common Factor (HCF) of the numbers 24 36 = 12

**Explanation:**

The findGcd() function is called with two integers stored in variables number1 and number2. The function computes and returns the H.C.F. of these two integers.

Because the H.C.F can only be less than or equal to the lowest number, we first find the smaller of the two integers in the function. Then, to move from 1 to that number, we utilize a for loop.

We check if our number divides both input numbers precisely in each cycle. If this is the case, the number is saved as H.C.F. We wind up with the greatest integer that divides both numbers properly at the end of the loop.

The method described above is simple to learn and apply, but it is inefficient. The Euclidean algorithm is a significantly more efficient technique of calculating the H.C.F.

### Method #2:Using Euclidean algorithm

**gcd in python: **This approach is based on the fact that the H.C.F. of two numbers also divides their difference.

We divide the greater by the smaller and take the remainder in this algorithm. Divide the smaller number by the remainder. Repeat until the residual equals zero.

**Facts of Euclidean Algorithm:**

GCD does not change when we subtract a smaller number from a larger number (we reduce a larger number). So, if we keep subtracting the largest of two numbers, we get GCD.

Instead of subtracting, we can divide the smaller integer, and the procedure will terminate when we find a remainder of zero.

**Algorithm:**

- Let number1 and number2 be the two numbers in the pseudocode of the algorithm.
- number1 mod number2 =R
- Assume that number1= number2 and number2 = R.
- Continue with Steps 2 and 3 until number1 mod number2 is greater than 0.
- GCD = number2
- Print the GCD

**Below is the implementation:**

# function which computes and returns the highest common factor of the given two numbers def findGcd(number1, number2): while(number2): number1, number2 = number2, number1 % number2 return number1 # given two numbers # given number a number1 = 24 # given number b number2 = 36 # passing the given two numbers to findGcd function which returns the greatest common factor of the given two numbers ans = findGcd(number1, number2) # print the hcf of the given two numbers print("The Highest Common Factor (HCF) of the numbers", number1, number2, "=", ans)

**Output:**

The Highest Common Factor (HCF) of the numbers 24 36 = 12

### Explanation:

We’ll keep looping until y equals zero. In Python, the statement number1, number2 = number2, number1 % number2 swaps values.

In each iteration, the value of number2 is placed in number1 and the remainder (number1 % number2) is placed in number2. We have H.C.F. in number1 when number2 becomes zero.

### Method #3:Using gcd() function in math module

This is the simplest and quick method to calculate the greatest common divisor of the given two numbers.

**Approach:**

- Import the math module
- Use math.gcd(number1,number2) to calculate the gcd of the numbers number1 and number2.
- Print the result.

**Below is the implementation:**

# importing math module import math # function which computes and returns the highest common factor of the given two numbers def findGcd(number1, number2): # calculating gcd using gcd() function resGcd = math.gcd(number1, number2) # return the gcd of the number 1 and number2 return resGcd # given two numbers # given number a number1 = 24 # given number b number2 = 36 # passing the given two numbers to findGcd function which returns the greatest common factor of the given two numbers ans = findGcd(number1, number2) # print the hcf of the given two numbers print("The Highest Common Factor (HCF) of the numbers", number1, number2, "=", ans)

**Output:**

The Highest Common Factor (HCF) of the numbers 24 36 = 12

**Explanation :**It just calculated the gcd in 1 line which is math.gcd()

**Related Programs**:

- python program to calculate the standard deviation
- python program to calculate the hcf gcd
- python program to calculate the average of numbers in a given list
- python program to calculate the length of a string without using a library function
- python program to calculate the number of words and the number of characters present in a string
- python program to calculate the number of digits and letters in a string
- python program to find the factorial of a number