Euclid’s Algorithm

Euclid's Algorithm is a method for finding the greatest common divisor (GCD) of two integers. The algorithm is based on the observation that if we subtract the smaller number from the larger number, the GCD of the two numbers does not change. We repeat this process until both numbers become equal, which is the GCD.

Here is the pseudocode for Euclid's Algorithm:

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

In this algorithm, `a` and `b` are the two integers whose GCD we want to find. The `mod` operator returns the remainder when `a` is divided by `b`. The algorithm works by repeatedly dividing the larger number by the smaller number, and replacing the larger number with the remainder until the remainder is zero. At this point, the GCD is the last non-zero remainder.