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