Skip to content
Home » C Program For GCD Of Two Numbers

C Program For GCD Of Two Numbers

    This is a simple program to find the Greatest Common Divisor (GCD) of two given positive numbers.

    We wrote and compiled the program on Dev-C++ version 5( beta) compiler installed on a Windows 7 64-bit machine. If you want to try a different C compiler, make sure to modify the existing source code to get an error-free program.

    Learn following c programming topics before you try the example program.

    Problem Definition

    Suppose you want to find GCD of two numbers – a and b. The C program for GCD has a function called hcf(a, b) which is called recursively until remainder is 0. The function uses the following logic on the given input numbers where a is greater than or equal to b.

    \begin{aligned}
&r = a - (a/b * b)
\end{aligned}

    Suppose a = 24 and b = 6 than

    \begin{aligned}
&r = 24 - (24/6 * 6)\\ 
&r = 24 - 24 = 0\\
&r = 0
\end{aligned}

    Then the value of b is the GCD which is 6. Note: – number a must be greater than or equal to b.

    Flowchart – Program for GCD of Two Numbers

    Flowchart - C Program for GCD of Two Numbers
    Figure 1 = Flowchart – C Program for GCD of Two Numbers

    Program Code – Program for GCD of Two Numbers

    #include <stdio.h>
#include <conio.h>
main()
{
    int i,a,b,gcd;
    int hcf();
    /* Read the input numbers */
    printf("Enter Two Numbers To Find GCD:");
    scanf("%d%d",&a,&b);
    /* Compute the GCD for given numbers */
    gcd=hcf(a,b);
    /* Print the Result */
    for(i=0;i<40;i++)
    printf("_");printf("\n\n");
    printf("GCD of %d and %d is %d\n",a,b,gcd);
    for(i=0;i<40;i++)
    printf("_");printf("\n\n");
    system("PAUSE");
    return 0;
}

int hcf(p,q)
{
    int r;
    r=p-(p/q*q);
    if(r==0)
        return(q);
    else
        return hcf(q,r);
}

    The important piece of code in the above source code is the call to hcf(a, b) function and the function hcf(a, b) calling itself recursively.

    gcd = hcf(a, b);

    The function hcf(a, b) evaluate the current value of a and b, and if the remainder is not equal to 0, it call itself one more time until the remainder becomes 0.

    int hcf(p,q) 
{  
    int r; 
    r=p-(p/q*q);  
    if(r==0)  
        return(q);  
    else  
        return hcf(q,r); 
}

    Output

    The output of the program is given below. When the user enters 24 and 6, the result is 6 which greatest common divisor (GCD) of 24 and 6.

             Enter Two Numbers To Find GCD:24 6
          ------------------------------------------
          GCD of 24 and 6 is 6
          ------------------------------------------
    Tags: