# Program to calculate the GCD of two numbers in C

## Program Description:

In this article, We are going to write a program to calculate the GCD of two numbers in C Language. The GCD or Greatest common divisor of two numbers is The largest Integer that evenly divides each of the integers. The program should accept two positive integers from the user and display the Greatest common divisor ( GCD ) of the given numbers.

Before going to write the program, We should understand what is GCD and how we calculate GCD.

## What is Greatest Common Divisor (GCD)?

The GCD or greatest common divisor of two numbers is The largest positive Integer that evenly divides each of the integers.

For example, the GCD of the number 80 and number 30 is 10. As the number 10 is the Largest Factor of both 80 and 30 numbers.

gcd(80, 30 ) = 10

We have already discussed about the Program to find all Factors of a number in earlier posts.

ðŸ“¢The Greatest Common Divisor (GCD) is the Highest Common Factor or HCF.

ToÂ helpÂ youÂ understandÂ better,Â hereÂ areÂ aÂ fewÂ numbersÂ andÂ theirÂ GreatestÂ CommonÂ Divisors.

## Example Inputs and Outputs of Program:

Input:

Enter two positive numbers : 1000 450

Output:

GCD or HCF of 1000 and 450 is 50

## GCD Program Pre-Requisites:

We are going to use C Loops and Modulus operator. So it is a good idea to have knowledge of these topics. Please go through the following articles to learn more about the above topics.

## GCD of two numbers in C Program Algorithm:

1. Start the program by taking input from the user. Accept two numbers from the user and store them in variables called num1 and num2
2. No GCD for negative numbers, So Check if any of the num1 or num2 is a negative number. If so display an error message â€“ Invalid Input, Please provide valid numbers and terminate the program using the return
3. The GCD of a number is the largest number that evenly (perfectly) divides the given numbers. So letâ€™s loop from 1 to min(num1, num2) using variable i.
• At each iteration, check if i evenly divide both num1 and num2 using modulus operator â€“ ( (num1 % i == 0) && (num2 % i == 0) )
• If the above condition is True, Then the i is Factor of num1 and num2 , So update the gcd variable.
• Increment i using i++
4. Once we came out of the loop the gcd variable will contains the Greatest Common Divisor (GCD) or HCF

## GCD of two numbers in C Language using while loop:

Here is the C implementation of the above algorithm.

### Program Output:

Save the program and compile and run it.

Letâ€™s check the GCD of positive numbers

As you can see from the above output, As expected, We are getting the GCD or HCF of the two numbers.

Letâ€™s check the negative numbers cases.

If the user provides a negative number, Then the program displays the error message â€“ Invalid Input, Please provide valid numbers.

## Alternative Method: HCF or GCD of two numbers in C using while loop:

We are going to slightly modify the above program to loop until the min of two number num1 and num2.

The above program also technically does that, Letâ€™s do it explicitly using by calculating the minimum of given two numbers using the Conditional Operator

int min = (num1 &gt; num2) ? num2: num1;

Here is the full program

### Program Output:

Compile and Run the program using the GCC compiler.

## Greatest Common Divisor or GCD of two numbers in C using for loop and Goto Statement:

Letâ€™s re-write the above program by using the for loop and the Goto Statement. Use goto statement to allow the user to provide the input number again.

### Program Output:

Letâ€™s test the program.

As you can see from the above output, The program is displaying an error message on a negative number and also allowing the user to provide the input numbers again. This process continues until the user enters valid positive numbers.

Venkatesh

Hi Guys, I am Venkatesh. I am a programmer and an Open Source enthusiast. I write about programming and technology on this blog.

### 5 Responses

1. [â€¦] the GCD or Greatest Common Divisor of two numbers. â€“ Here is the formula to calculate the LCM based on [â€¦]

2. [â€¦] C Program to Calculate the GCD or HCF of Two Number [â€¦]

3. [â€¦] C Program to Calculate the GCD or HCF of Two Number [â€¦]

4. [â€¦] C Program to Calculate the GCD or HCF of Two Number [â€¦]

5. [â€¦] C Program to Calculate the GCD or HCF of Two Number [â€¦]