C Program to Find GCD of Two Numbers

Today we will learn How to write C Program to Find GCD of Two Numbers and also learn C program to find GCD of two numbers using Recursion. Before Learning we will do a quick overview of GCD concept.

Table of Contents

What is GCD?

GCD stands for Greatest Common Divisor. The GCD of two or more integers(other than zero), which is the largest positive integer that divides both the integers.

For Example, GCD of 6 and 4 is 2.

There are different ways to find GCD of two numbers we will see it one by one.

1. C Program to Find GCD of Two Numbers Using For loop

In this program, the compiler will ask the user to enter the two numbers that the user wants to find it’s GCD. After the user enters the program start executing and prints the output on the screen.

#include<stdio.h>
void main()
{
    int n1,n2,i,min,GCD;
    printf("Enter two integers to find their GCD: \n ");
    scanf("%d%d",&n1,&n2);
    min = (n1<n2)?n1:n2;
    for(i=1;i<=min;i++)
    {
        // Checks if i is factor of n1 &n2 
        if(n1%i==0 && n2%i==0)
        {
            GCD = i;
        }
    }
    printf("\n G.C.D of %d and %d is %d", n1, n2, GCD);
}

Output:

Explanation:

1st Iteration: for(i=1;i<=min;i++) i.e for(i=1;1<=4;i++) and if(n1%i==0 && n2%i==0) i.e (4%1==0 && 6%1==0) is TRUE then the value of GCD becomes 1 i.e GCD=1.

2nd Iteration: for(i=2;i<=min;i++) i.e for(i=2;2<=4;i++) and if(n1%i==0 && n2%i==0) i.e (4%2==0 && 6%2==0) is TRUE then the value of GCD becomes 2 i.e GCD=2.

3rd Iteration: for(i=3;i<=min;i++) i.e for(i=3;3<=4;i++) and if(n1%i==0 && n2%i==0) i.e (4%3==0 && 6%3==0) is FALSE then the below statements are not executed.

4th Iteration: for(i=4;i<=min;i++) i.e for(i=4;4<=4;i++) and if(n1%i==0 && n2%i==0) i.e (4%4==0 && 6%4==0) is FALSE then the below statements are not executed.

5th Iteration: as i is incremented so the value of i becomes 5 and the loop is exited because of 5>4. So finally the value of GCD becomes 2.

2. C Program to Find GCD of Two Numbers Using While loop

In this program, we will use while loop instead of for loop. Don’t be afraid of changing loop logic behind the program is same.

#include <stdio.h>
int main()
{
    int n1, n2;
    printf("Enter two positive integers to check GCD: ");
    scanf("%d %d",&n1,&n2);
    while(n1!=n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    printf("GCD = %d",n1);
    return 0;
}

Output:

3. GCD of two numbers Using Temporary Variable

In this program, we will use the Temporary Variable to calculate GCD of the entered number by the user.

#include <stdio.h>
int main()
{
    int Num1, Num2, GCD;
    printf("Please Enter two integer Values to find GCD \n");
    scanf("%d %d", &Num1, &Num2);
	if (Num1 == 0) {
  		printf("GCD = %d", Num2);
  	}
 	while (Num2 != 0) {
    	if (Num1 > Num2) {
      		Num1 = Num1 - Num2;
    }
    	else {
      		Num2 = Num2 - Num1;
    	}
  	}
  	GCD = Num1;
    printf("GCD = %d", GCD);
    return 0;
}

Output:

4. GCD of both Positive and Negative Number

In this program when the user enters the negative number then that negative number is first converted into positive then the GCD is printed on the screen.

#include <stdio.h>
int main()
{
    int n1, n2;
    printf("Enter two integers to find GCD: ");
    scanf("%d %d",&n1,&n2);
    // if user enters negative number, sign of the number is changed to positive
    n1 = ( n1 > 0) ? n1 : -n1;
    n2 = ( n2 > 0) ? n2 : -n2;
    while(n1!=n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    printf("GCD = %d",n1);
    return 0;
}

Output:

5. Gcd of Two Numbers using Recursion

Recursion is the method in which the function calls itself symmetrically or asymmetrically. Now we will see how GCD program is written Using Recursion.

#include <stdio.h>
long gcd(long x, long y);
int main()
{
    int Num1, Num2;
    printf("Please Enter two integer Values \n");
    scanf("%d %d", &Num1, &Num2);
    printf("GCD of %d and %d is = %d", Num1, Num2, gcd(Num1, Num2));
    return 0;
}
long gcd(long x, long y) 
{
  if (y == 0) {
  	return x;
  }
  else {
    return gcd(y, x % y);
  }
}

Output:

6. GCD program using function

In this program, we will use a function called gcd() and find the gcd of two numbers using the function. Now let us see how the function works.

#include <stdio.h>
long gcd(long x, long y);
int main()
{
    int Num1, Num2;
    printf("Please Enter two integer Values \n");
    scanf("%d %d", &Num1, &Num2);
    printf("GCD of %d and %d is = %d", Num1, Num2, 	gcd(Num1, Num2));
    return 0;
}
long gcd(long x, long y) 
{
	if (x == 0) {
  		return y;
  	}
 	while (y != 0) {
    	if (x > y) {
      		x = x - y;
    }
    	else {
      		y = y - x;
    	}
  	}
  	return x;
}

Output:

7. C Program to find GCD of n Numbers Simultaneously

Till now we find GCD using two numbers but in this program, we will ask the user to enter n numbers and their gcd will be printed on the screen after execution.

#include<stdio.h>
int main()
{
    printf("\nLearnprogramo-Programming made Simple\n\n\n");
    int x, y =- 1;
    printf("Enter numbers. and press 0 to exit program\n");
    while(1)    // infinite loop to take input
    {
        scanf("%d", &x);
        if(x < 1)
            break;
        else if(y ==- 1)    // only 1 number entered, its GCD is itself
            y = x;
        else if(x < y)
            y = gcd(x, y);
        else
            y = gcd(y, x);
    }
    printf("\n\n\nGCD of all the entered number is: %d", y);
    return 0;
}
// GCD of 2 numbers is calculated at a time
int gcd(int a, int b) 
{
    int i;
    /*
        a is the smallest of the two numbers 
        of which GCD is to be calculated
    */
    for(i = a; i >= 1; i--) 
    {
        // Greatest number that divides both the numbers
        if(a%i == 0 && b%i == 0) 
            break;  // exits the loop
    }
    return i;
}

Output: