The greatest common divisor of two numbers is the largest number that divides evenly into both numbers.

The method of calculating this is is to use a little bit of recursion.

If the numbers are even, then work out the GCD by dividing both numbers by 2 and passing as parameters to the GCD function recursively, multiplying the result by 2.

If only one number is even, then pass that number divided by 2, and the whole second number to the GCD function to get the GCD.

If both numbers are odd, then call the GCS function with the average of the two numbers and the second number as the parameters.

If the numbers are equal then return that number, and if either number is equal to then return 1.

By the time execution reached the top again after the recursion, you should have the greatest common divisor as your resulting number.

        public static int GCD(int A, int B)
        {
            if (A == B)
            {
                return A;
            }
            if ((A == 1) || (B == 1))
            {
                return 1;
            }
            if ((A % 2 == 0) && (B % 2 == 0))
            {
                return 2 * GCD(A / 2, B / 2);
            }
            else if ((A % 2 == 0) && (B % 2 != 0))
            {
                return GCD(A / 2, B);
            }
            else if ((A % 2 != 0) && (B % 2 == 0))
            {
                return GCD(A, B / 2);
            }
            else
            {
                return GCD(Math.Abs(A - B) / 2, B);
            }

        }
  • Share/Bookmark

Related posts:

  1. Finding the prime factors of a number in C# A prime number is any number that can only be...
  2. Maths algorithms in C#: The median The median is defined as the data point that falls...
  3. Maths algorithms in C#: The geometric mean The geometric mean is similar to the arithmetic mean in...
  4. Maths algorithms in C#: Standard deviation Standard deviation is a very common calculation in statistical analysis,...
  5. Finding the distance between two GPS coordinates With the advent of GPS systems, adn mapping systems like...

Related posts brought to you by Yet Another Related Posts Plugin.