65.9K
CodeProject is changing. Read more.
Home

Fast Greatest Common Divisor (GCD) Algorithm

starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.50/5 (2 votes)

Feb 11, 2011

CPOL
viewsIcon

8321

Can we simplify it by: (This essentially passes only two numbers). public int GCD(int value1, int value2){ int max = 0; bool gcdFound = false; int counter = 1; //Make sure both numbers are atleast 2 or above if (( value1 <= 1 ) || (value2 <= 1)) return...

Can we simplify it by: (This essentially passes only two numbers).
public int GCD(int value1, int value2)
{

    int max = 0;
    bool gcdFound = false;
    int counter = 1;

    //Make sure both numbers are atleast 2 or above
    if (( value1 <= 1 ) || (value2 <= 1))
        return (value1 < value2 ? value1 : value2);

    //If one of the two numbers is the exact divisor of then other or are equal to each other then we return that number here.
    gcdFound = (((value1 % value2 ) == 0 ) || ((value2 % value1 ) == 0 ));
    if (gcdFound)
    {
        return (value1 > value2 ? value2 : value1);
    }

    //Find the larger of the two numbers, the GCD can not be more than half of the smaller number.
    max =  value1 > value2 ? (value2 / 2) : (value1 / 2);
    counter = max + 1;

    while ((!gcdFound) && (counter > 1))
    {
        counter--;
        gcdFound = ((value1 % counter) == 0) && ((value2 % counter) == 0);
    }

    return counter;
}