by Dinesh Thakur Category: Control Structures

Let us use variables m and n to represent two integer numbers and variable r to represent the remainder of their division, i. e., r = m % n. Euclid's algorithm to determine the GCD of two numbers m and n is given below and its action is illustrated form= 50 and n = 35.

while (n > 0)

    {

        int r = m % n;

        m = n;

        n = r;

    }

      C Program for GCD using Euclid’s algorithm

In each iteration of this loop, we determine the remainder (r = m % n) and assign current values of variables n and r to variables m and n, respectively. Execution is continued as long as the value of divisor n is greater than zero. When the value of n becomes zero, the value of variable m is the GCD of the given numbers as indicated above. The complete program is given below.

/* GCD of two numbers using Euclid's algorithm*/

#include <stdio.h>

void main()

{

    int m, n; /* given numbers */

    clrscr();

    printf("Enter-two integer numbers: ");

    scanf ("%d %d", &m, &n);

    while (n > 0)

    {

        int r = m % n;

        m = n;

        n = r;

    }

    printf ("GCD = %d \n",m);

    getch();

}

     GCD using Euclid’s algorithm



About Dinesh Thakur

Dinesh ThakurDinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.



Search Content





Popular Article