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.

r = a - (a/b * b)  

suppose a = 24 and b = 6, than

r = 24 - (24/6 * 6)    r = 24 - 24 = 0    r = 0

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
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.

Output - C Program for GCD of Two Numbers
Output – C Program for GCD of Two Numbers

Related Articles:

Advertisements