Gcd

Euclidean algorithm

gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)

Recursive:

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

Iterative:

int gcd(int a, int b) {
    if (b) while ((a %= b) && (b %= a));
    return a + b;
}

C++ Built-in function

C++ has a built-in __gcd function.

__gcd(6, 20); // 2

Since C++11, we can directly use gcd.

Time Complexity

https://www.geeksforgeeks.org/time-complexity-of-euclidean-algorithm/

It's O(log(min(A, B)))

Problems

PreviousFast PowNextGeometry

Last updated