Program to calculate the GCD of two numbers in C
- Program Description:
- What is Greatest Common Divisor (GCD)?
- Example Inputs and Outputs of Program:
- GCD Program Pre-Requisites:
- GCD of two numbers in C Program Algorithm:
- GCD of two numbers in C Language using while loop:
- Alternative Method: HCF or GCD of two numbers in C using while loop:
- Greatest Common Divisor or GCD of two numbers in C using for loop and Goto Statement:
- Related Programs:
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.
| Two Numbers | GCD |
|---|---|
| 25, 70 | 5 |
| 4, 9 | 1 |
| 60, 90 | 30 |
| 2, 10 | 2 |
| 12354, 82492 | 2 |
| 45, 9 | 9 |
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.
- Modulus Operator in C Language with Example Programs
- While Loop in C with Example Programs
- For Loop in C Language with Programs
- Goto Statement in C and it’s Usage
GCD of two numbers in C Program Algorithm:
- Start the program by taking input from the user. Accept two numbers from the user and store them in variables called num1 and num2
- 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
- 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++
- 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
/*     Program: GCP or HCF program in C using while loop     Author: SillyCodes.com */ #include<stdio.h> int main() {     int num1, num2, gcd;      // Take the input from the user     printf("Enter two positive numbers : ");     scanf("%d%d", &num1, &num2);      // num1 and num2 must be positive numbers     if(num1 <= 0 || num2 <= 0) {         printf("Invalid Input, Please provide valid numbers \n");         return 0;     }      int i = 1;         while(i<=num1 && i <=num2)     {         // check if the 'i' is factor of 'num1' and 'num2'         if(num1 % i == 0 && num2 % i == 0)         {             // update the 'gcd'             gcd = i;         }          // increment counter 'i'         i++;     }      // print the GCD     printf("GCD or HCF of %d and %d is %d \n", num1, num2, gcd);      return 0; } |
Program Output:
Save the program and compile and run it.
Let’s check the GCD of positive numbers
|
1 2 3 4 5 6 7 8 9 10 11 |
$ gcc gcd.c $ ./a.out Enter two positive numbers : 60 20 GCD or HCF of 60 and 20 is 20 $ ./a.out Enter two positive numbers : 35 5 GCD or HCF of 35 and 5 is 5 $ ./a.out Enter two positive numbers : 10 100 GCD or HCF of 10 and 100 is 10 $ |
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.
|
1 2 3 4 5 6 7 |
$ ./a.out Enter two positive numbers : -6 2 Invalid Input, Please provide valid numbers $ ./a.out Enter two positive numbers : 10 -100 Invalid Input, Please provide valid numbers $ |
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 > num2) ? num2: num1;
Here is the full program
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
/*     Program: GCP or HCF program in C using while loop     Author: SillyCodes.com */ #include<stdio.h> int main() {     int num1, num2, gcd;      // Take the input from the user     printf("Enter two positive numbers : ");     scanf("%d%d", &num1, &num2);      // num1 and num2 must be positive numbers     if(num1 <= 0 || num2 <= 0) {         printf("Invalid Input, Please provide valid numbers \n");         return 0;     }      int i = 1;         // we can simply loop until the min of two     int min = (num1 > num2) ? num2: num1;      while(i<=min)     {         // check if the 'i' is factor of 'num1' and 'num2'         if(num1 % i == 0 && num2 % i == 0)         {             // update the 'gcd'             gcd = i;         }          // increment counter 'i'         i++;     }      // print the GCD     printf("GCD or HCF of %d and %d is %d \n", num1, num2, gcd);      return 0; } |
Program Output:
Compile and Run the program using the GCC compiler.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
$ ./a.out Enter two positive numbers : 40 15 GCD or HCF of 40 and 15 is 5 $ ./a.out Enter two positive numbers : -29 10 Invalid Input, Please provide valid numbers $ ./a.out Enter two positive numbers : 24 8 GCD or HCF of 24 and 8 is 8 $ ./a.out Enter two positive numbers : 54 9 GCD or HCF of 54 and 9 is 9 $ ./a.out Enter two positive numbers : 1000 450 GCD or HCF of 1000 and 450 is 50 $ ./a.out Enter two positive numbers : 10 -5 Invalid Input, Please provide valid numbers $ |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/*     Program: GCP or HCF program in C using for loop     Author: SillyCodes.com */ #include<stdio.h> int main() {     int num1, num2, gcd, i;      // goto statement Label     START:      // Take the input from the user     printf("Enter two positive numbers : ");     scanf("%d%d", &num1, &num2);      // num1 and num2 must be positive numbers     if(num1 <= 0 || num2 <= 0) {         // Display Error         printf("Invalid Input, Please provide valid numbers \n");          // jump to start of the program 'START' label.         goto START;     }         // we can simply loop until the min of two     int min = (num1 > num2) ? num2: num1;      // Loop from '1' to 'min'     for(i = 1; i <= min; i++) {          // check if the 'i' is factor of both 'num1' and 'num2'         if(num1 % i == 0 && num2 % i == 0)         {             // update the 'gcd'             gcd = i;         }     }      // print the GCD     printf("GCD or HCF of %d and %d is %d \n", num1, num2, gcd);      return 0; } |
Program Output:
Let’s test the program.
|
1 2 3 4 5 6 7 8 |
$ gcc gcd.c $ ./a.out Enter two positive numbers : 60 15 GCD or HCF of 60 and 15 is 15 $ ./a.out Enter two positive numbers : 90 50 GCD or HCF of 90 and 50 is 10 $ |
what about the negative numbers
|
1 2 3 4 5 6 7 8 |
$ ./a.out Enter two positive numbers : -4 10 Invalid Input, Please provide valid numbers Enter two positive numbers : 40 -23 Invalid Input, Please provide valid numbers Enter two positive numbers : 80 30 GCD or HCF of 80 and 30 is 10 $ |
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.
Related Programs:
- If else practice Programs
- Switch Case Practise Programs
- Convert Binary number to Decimal Number in C
- C program to test Leap yearÂ
- C program to Find Area and Perimeter of Rectangle.
- Calculate the Grade of Student.
- Temperature Conversion program in C. ( Centigrade to Fahrenheit ).
- Type Conversion Operators on Assignment operator.
- Prime Numbers up to n
- Calculate Sum of Digits Program in C
- Octal to Decimal Number Conversion
5 Responses
[…] the GCD or Greatest Common Divisor of two numbers. – Here is the formula to calculate the LCM based on […]
[…] C Program to Calculate the GCD or HCF of Two Number […]
[…] C Program to Calculate the GCD or HCF of Two Number […]
[…] C Program to Calculate the GCD or HCF of Two Number […]
[…] C Program to Calculate the GCD or HCF of Two Number […]