GCD of two numbers in C
In this article, you will learn to find the greatest common divisor (G.C.D) or highest common factor (H.C.F) of numbers in different methods using C programming.
Greatest common divisor (G.C.D) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers a, b, the greatest common divisor of a and b is denoted gcd(a,b). These are different ways to find the GCD or HCF using Java -
GCD in C using for loop
Here, we define a function to compute the G.C.D of two numbers, x and y and return it. In each iteration, we check if our number perfectly divides both the given numbers. If this is true, we store the number as H.C.F. At the completion of the loop, we conclude with the largest number that perfectly divides both the numbers.
#include <stdio.h>
int main()
{
int x, y, i, gcd;
printf("Enter two integers: ");
scanf("%d %d", &x, &y);
for(i=1; i <= x && i <= y; ++i)
{
if(x%i==0 && y%i==0)
gcd = i;
}
printf("G.C.D of %d and %d : %d", x, y, gcd);
return 0;
}
Output of the above code:
Enter two integers: 4 10
G.C.D of 4 and 10 : 2
GCD in C using while loop
In the given C program, we have used the while loop to find the G.C.D of two numbers. In this method, the smaller integer is subtracted from the larger integer, and the result is assigned to the variable holding the larger integer. This process is continued until the condition x!=y becomes false.
#include <stdio.h>
int main()
{
int x, y, i, gcd;
printf("Enter two integers: ");
scanf("%d %d", &x, &y);
while(x!=y)
{
if(x > y)
x = x-y;
else
y = y-x;
}
printf("GCD of the given numbers : %d",x);
return 0;
}
Output of the above code:
Enter two integers: 20 34
GCD of the given numbers : 2
Enter two integers: 13 89
GCD of the given numbers : 1
GCD in C using recursion
Recursion function is a function which is calling itself. The following code finds the greatest common divisor of user inputs using the recursion function. A recursion function continues until some condition is met to prevent it. That's why we use the if statement to break the infinite recursion.
#include <stdio.h>
int compute_gcd(int x, int y);
int main()
{
int x, y;
printf("Enter two positive numbers: \n");
scanf("%d %d", &x, &y);
// calling function compute_gcd()
printf("GCD of two numbers %d and %d : %d", x, y, compute_gcd(x, y));
}
int compute_gcd(int num1, int num2)
{
if (num2 != 0)
{
return compute_gcd( num2, num1 % num2);
}
else
{
return num1;
}
}
Output of the above code:
Enter two integers: 20 34
GCD of the given numbers : 2
Enter two integers: 13 89
GCD of the given numbers : 1
GCD in C using user defined function
Here, we have defined user function to compute the G.C.D. of two entered numbers.
#include <stdio.h>
void main()
{
// declaration of local variable
int x , y;
printf("Enter the first number: ");
scanf("%d", &x);
printf("Enter the second number: ");
scanf("%d", &y);
printf("GCD of two number %d and %d: %d", x, y, compute_gcd( x, y));
}
// User-defined function
// to find gcd of two numbers
int compute_gcd(int a, int b)
{
int hcf;
for(int i=1; i<=a && i<=b; i++)
{
if(a%i==0 && b%i==0)
{
hcf = i;
}
}
return hcf;
}
Output of the above code:
Enter the first number: 45
Enter the second number: 33
GCD of two number 45 and 33: 3
Related Articles
Prime factors of a number in cArmstrong number program in c
Write a program to check leap year in c
C program to find area of rectangle
C program to convert celsius to fahrenheit
Fibonacci series program in C using recursion
Write a program to find area of circle in C
C program to find greatest of three numbers
C program for addition of two numbers
C program to calculate compound interest
C program to find the ASCII value of a character
C program to convert Decimal to Octal
C program to convert decimal to binary
Write a C program to calculate Simple Interest
C program to check whether a number is even or odd
C program to reverse a number
C program to check palindrome number
C program to check whether an alphabet is a vowel or consonant
Program to find square root of a number in C
C program to check whether a number is positive or negative