Euclid's Algorithm

Euclid’s algorithm is an efficient method for computing the greatest common divisor (GCD) of two numbers. It is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number.

Java example:

1
2
3
4
5
6

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b); 
}

int d = gcd(48, 18); // Returns 6

C++ example:

1
2
3
4
5
6

int gcd(int a, int b) {
  if (b == 0) return a;  
  return gcd(b, a % b);
}

int d = gcd(48, 18); // Returns 6

Python example:

1
2
3
4
5
6

def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a % b)
  
d = gcd(48, 18) # Returns 6

The algorithm works by recursively computing the GCD of the remainder and smaller number. The base case is when the smaller number becomes 0, indicating the current larger number is the GCD.

Euclid’s algorithm is an efficient way to find the greatest common factor of two integers, with runtime O(log(min(a, b))).

Euclid’s algorithm is a method for finding the Greatest Common Divisor (GCD) of two integers. The algorithm is based on the principle that the GCD of two numbers (a) and (b) (where (a > b)) is the same as the GCD of (b) and (a \mod b).

Example Code in Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public class EuclidsAlgorithm {
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        int a = 252, b = 105;
        System.out.println("GCD of " + a + " and " + b + " is " + gcd(a, b));
    }
}

Example Code in C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int a = 252, b = 105;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b) << endl;
    return 0;
}

Example Code in Python

1
2
3
4
5
6
7

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

a, b = 252, 105
print(f"GCD of {a} and {b} is {gcd(a, b)}")

In each of these examples, the function gcd computes the greatest common divisor of two integers (a) and (b). The function employs recursion, invoking itself with new arguments (b) and (a \mod b) until (b) becomes zero. At that point, (a) is the GCD of the original (a) and (b).