GCD program of two numbers in C

GCD stands for Greatest Common Divisor, which is also known as Highest Common Factor, which can be abbreviated as HCF. Mathematically it can be defined as any two positive integers having the greatest positive number, which is a common factor of two given positive integers and is known GCD of two numbers. The GCD of two numbers can never be negative or 0, and 1 is the least common factor of two positive integers.

The mathematical process to find GCD:

Using the LCM method, we can obtain the GCD of two numbers by finding the product of two numbers and dividing with the LCM of that two numbers.

Using the Prime factorization method, each integer is written as the product of prime numbers, then find the product of the smallest power of each common factor.

Using Long Division Method, the biggest number in a given set of numbers needs to be divided by the second largest number, and then the second largest number needs to be divided by the remainder of the previous operation. This process continues until the remainder becomes zero. The divisor, which is obtained while doing remainder zero is known as the greatest common divisor of the given positive integers.

This mathematical process of finding GCD can be performed by a system or computer by writing a program.

Program for GCD of Two numbers

#include<stdio.h>
int main()
{
	int a, b;
	printf(“Enter only two positive integers: “);
	scanf(“%d%d”, &a, &b);
	while(a!=b)
	{
		if(a > b)
			a -= b;
		else
			b -= a;
	}
	printf(“GCD of given two numbers is: %d”, a);
	return 0;
} 

Output

The above code can be used as the calculator for finding the common factor of two positive integers, which simplifies the work.

Explanation of the above program:

We use #include<stdio.h> to import standard input and output functions like scanf, printf, puts, gets, etc. The role of it is to declare the integer type variables and used to initialize the variable (the location where we store data), and we can also initialize different datatypes like float (for decimals), char (for letters and symbols), etc.

Here we declared two variables, a and b that are initialized. We used the printf() function to display what to enter, and we used the scanf() function to take two integer values. We used a looping statement called the while() function in which we keep a condition a not equal to b, and we use conditional statements if() and else() functions and specify the condition a greater than b in the if condition. We use some assignment operators who will store the value in a and b.

Note: The while loop is going to be executed until a is equal to b and the print a value.

The different approaches of programming GCD of two numbers:

#include<stdio.h>
int main()
{
   	int a, b, remainder;
   	printf("enter any two numbers:");
   	scanf("%d%d", &a, &b);
   	while(b!=0)
{
      		remainder=a % b;
     		a=b;
      		b=remainder;
   	}
   	printf("GCD of two numbers is given by:%d", a);
   	return 0;
}

Output

Explanation for the above Program:

The above code is another approach to solving the GCD (Greatest Common Divisor) of two numbers by means of remainders. The logic we use is GCD of two numbers is the largest number which exactly divides both the integer with no remainder left.

Initializing three integer values, namely a, b, and remainder. Giving input for two variables, a and b, we are going to iterate the while loop until we get b=0, which means the remainder should become zero. Then we can print that b value which gives the GCD of two numbers.

Program using Functions along with while loop:

#include <stdio.h>  
#include <conio.h>  
INTGCD (int x, int y);   
int main()  
{  
    int x, y, GCD = 0;  
    printf("Enter two positive numbers:");
    scanf ("%d%d", &x, &y);   
    GCD = INTGCD( x, y);  
    printf ( " GCD of the two numbers %d and %d is %d", x, y, GCD);   
    getch();  
}  
  INTGCD ( int x, int y)  
{  
    while (y != 0)  
    {
	  	if ( x > y) 
			x = x - y;  
       	else  
          	y = y - x;  
    }  
    return x;  
}

Output