Search code examples
algorithmprime-factoringgreatest-common-divisor

Which approch is better

Which approach gives better time complexity to find GCD(a,b) of a given number?

Prime factorization

(or)

the below approach

int gcd(int a, int b)
{
    return (b==0)?a:gcd(b,a%b);
}
Solution

  • It depends on the range of your input as well as your implementation of Prime factorization. Since there's no efficient algorithm for large numbers for the latter, it seems like GCD can be implemented to provide more efficient results.

    The main point is how modulo is calculated in your algorithm - assuming it's being implemented efficiently (without using division) this implementation of GCD (also called Euclidean algorithm) should be more efficient.