Greatest Common Divisor (GCD) C++ Source Code

GCD or Greatest Common Divisor, is the number which can divide two or more numbers to zero (without remainder). or from wikipedia like this :

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), the greatest common denominator[1], or highest common factor (hcf), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

At this post, we will discuss three ways to solve the GCD (Greatest Common Divisor) problems. The first, we are going to search each integer number between the lower number to 1, if the number can devide two numbers, that’s the GCD. The second and third way, we use euclidean algorithm which using modulus operation :: GCD(a,b) = GCD(b, a mod b)

Okay, that’s just the preface… let’s get to C++ Source code. First, the header


#include <iostream>

using std::cout;
using std::cin;
using std::endl;

Then we define the function prototype


void swapInteger(int* a, int* b);
int gcdSearch(int a, int b);
int gcdEuclidIterative(int a, int b);
int gcdEuclidRecursive(int a, int b);

The function for swapping two integers is


void swapInteger(int* a, int* b){
     int swap = *a;
     *a = *b;
     *b = swap;
}

Now, the function of searching GCD


int gcdSearch(int a, int b){
    int low = 0;
    if (a < b) low = a;
    else low = b;

    for (int i=low;i>0;i--){
        if (a % i == 0 && b % i == 0)
        return i;
    }
}

Then, finding GCD using Iterative Euclidean Algorithm


int gcdEuclidIterative(int a, int b){
    if (a < b) swapInteger(&a, &b);
    int remainder = a % b;

    while (remainder != 0){
          a = b;
          b = remainder;
          remainder = a % b;
    }
    return b;
}

And the last, using Recursive Euclidean


int gcdEuclidRecursive(int a, int b){
    if (a < b) swapInteger(&a, &b);
    int remainder = a % b;

    if (remainder == 0) return b;
    else return gcdEuclidRecursive(b,remainder);
}

Leave a Reply

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

Post Navigation