C Example - Find the Greatest Common Divisor of Two Numbers

User inputs two numbers, and the program finds their greatest common divisor (GCD).

Example - Using for and if

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

    printf("Enter two positive integers, separated by a space: ");
    scanf("%d %d", &n1, &n2);

    for(i=1; i<= n1 && i<= n2; ++i)
    {
        // Check if i is the greatest common divisor
        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 positive integers, separated by a space: 81 153
GCD of 81 and 153 is 9

Example - Using while and if

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

    printf("Enter two numbers, separated by a space: ");
    scanf("%d %d",&n1,&n2);

    while(n1!=n2)
    {
        if(n1>n2)
            n1 -= n2;
        else
            n2 -= n1;
    }

    printf("GCD = %d",n1);
    return 0;
}

Output:

Enter two numbers, separated by a space: 81 153
GCD = 9

Example - Works for Positive and Negative Numbers

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

    printf("Enter two numbers, separated by a space: ");
    scanf("%d %d",&n1,&n2);

    // If input is negative, convert 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:

Enter two numbers, separated by a space: 81 -153
GCD = 9

Example - Using Recursion

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

int main()
{
    int n1, n2;

    printf("Enter two positive integers: ");
    scanf("%d %d", &n1, &n2);

    printf("GCD of %d and %d is %d", n1, n2, hcf(n1,n2));
    return 0;
}

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