Greatest common divisor code in C#

Reading Time: 1 minute

Greatest common divisor of two positive integer numbers N and M, both larger then zero is the largest integer R that divide both N and M. If for given N and M, greatest common divisor is 1, we say that N and M are relatively prime, or coprime. The easiest practical way for finding greatest common divisor is Euclidean algorithm, described as follows:

Step 1:

Compare N and M, and if M is larger then swap them so that N is made to be larger number.

Step 2:

Find reminder when N is dived with M ( R = N div M )

Step 3:

If reminder is greater then zero, then let N take value of M, M take value of R

Step 4:

Calculate R again as reminder of new N and M

Step 5:

Repeat steps 3 and 4 as long as R greater then zero.

Step 6:

Once when R reaches zero, return M as greatest common divisor.

Code is as follows:
static int GCD(int N, int M)

int R;
R = N % M;
while (R > 0)

N = M;
M = R;
R = N % M;

return M;

static void Main(string[] args)

int A = 518;
int B = 392;
int C = GCD(A, B);
Console.WriteLine(“{0}”, C);

Greatest common divisor can be used for reducing fractions and for finding least common multiple.

Calculate greatest common divisor online.

External links:

Greatest Common Divisor on Wikipedia
Greatest Common Divisor on Calculatorsoup
Greatest Common Divisor on Mathportal


Tagged with: ,

Leave a Reply

Your email address will not be published. Required fields are marked *