Euclidean Algorithm - Pseudocode

function gcd(a, b):

while b ≠ 0:

    temp = b

    b = a mod b

    a = temp

return a

The loop stops when b = 0. At that point, a holds the GCD. This runs in logarithmic time because each step cuts the numbers roughly in half.