Monday, 9 May 2016

Greatest common divisor

         In mathematics, the greatest common divisor(gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder(amount left over after peforming a division).

gcd(8, 12) = 4

         The greatest common divisor is also known as the greatest common factor(gcf), highest common factor(hcf), greatest common measure(gcm) or highest common divisor.

         I will present you the algorithm for this below:

#include <iostream>
using namespace std;

int gcd(int a, int b) // greatest common divisor of two numbers using repeated falls
    while(a != b) // while this two numbers are different
        if(a > b)
            a = a - b;
            b = b - a;
    return a; // greatest common divisor will be saved in first number

int main()
    cout<<gcd(8, 12);
    return 0;
There are 5 more methods to find gcd, more optimized. One of them complexity is best. Check bellow buttons(PayPal)!!!

Most optimized solution:

No comments:
Write comments