C Program to find GCD of two Numbers

The GCD of two integers is the largest integer that can exactly divide both numbers without a remainder.

There are many ways to implement this program and some of them are discussed below.

---

Using for loop:

#include<stdio.h>
int main()
{
    int n1, n2, i, gcd;
    
    printf("Enter two integers: ");
    scanf("%d %d", &n1, &n2);
    
    for(i=1; i<=n1 && i <=n2; i++)
    {
        if(n1 % i == 0 && n2 % i == 0)
        {
            gcd = i;
        }
    }
    printf("GCD of %d and %d is %d", n1, n2, gcd);
    return 0;
}

Output:
Enter two integers: 10
15
GCD of 10 and 15 is 5

Using while loop:

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

Output:
Enter two positive integers: 10
15
GCD is 5

Above program is a better way to find the GCD. In this method smaller integer is subtracted from the greater one, and the result is assigned to the var holding greater int. This process is continued until n1 and n2 are equal.

Using recursion:

#include<stdio.h>
int gcd(int n1,int n2);

int main()
{
    int n1, int n2;
    printf("Enter two positive integers: ");
    scanf("%d %d", &n1, &n2);
    printf("G.C.D of %d and %d is %d.", n1, n2, gcd(n1, n2));
    return 0;
}

int gcd(int n1, int n2)
{
    if(n2 !=0)
       return gcd(n2, n1 % n2);
    else
       return n1;
}

Output:
Enter two positive integers: 10
15
G.C.D of 10 and 15 is 5.

---

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #programming #gcd #placement_prep