# Euclidean algorithm

The Euclidean algorithm (also called Euclid's algorithm) is an algorithm to determine the greatest common divisor of two integers.

## Implementations

### C

Recursive version:

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

return gcd(b, a % b);
}
```
```C#

public static int TBH_GCD(int a, int b)
{
if(0==b)
return a;
else
return TBH_GCD(b,a%b);
}

```

Iterative version:

```int gcd(int a, int b) {
int t;
while (b != 0) {
t = b;
b = a % b;
a = t;
}
return a;
}
```

Version with loop-unrolling:

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

For normal C/C++ integers loop-unrolling does not make much difference; in the case of big integers (several hundreds of digits), however, it avoids the cost of unnecessary copies of the integers.

### C++

```#include <algorithm>
#include <cstdlib>

// Euclid's Algorithm for GCD
int GCD(int a, int b) {
// No negatives
a = abs(a);
b = abs(b);

// Ensure a >= b; can save a useless MOD
if (b > a) { std::swap(a, b); }

// Main loop of algorithm
int temp;
while (b > 0) {
temp = b;
b = a % b;
a = temp;
} // end while
return a;
} // end GCD()
```

### F#

Tail-recursive version (equivalent to an iterative version):

```> let rec gcd a = function
| 0 -> a
| b -> gcd b (a % b);;
val gcd : int -> int -> int
```

For example:

```> gcd 25 30;;
val it : int = 5
```

### OCaml

Tail-recursive version (equivalent to an iterative version):

```# let rec gcd a = function
| 0 -> a
| b -> gcd b (a mod b);;
val gcd : int -> int -> int = <fun>
```

For example:

```# gcd 25 30;;
- : int = 5
```

### Perl

<HIGHLIGHTSYNTAX language="perl"> use Math::Cephes qw(euclid); euclid(\$m, \$n); # returns GCD as first element </HIGHLIGHTSYNTAX>

### Python

Recursive version:

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

Iterative version:

```def gcd(a, b):
while b!=0:
a, b = b, a%b
return a
```

### PHP

Recursive version:

```function gcd(\$a, \$b) {
if (\$b == 0)
return \$a;
return gcd(\$b, \$a%\$b);
}
```

Iterative version:

```function gcd(\$a, \$b) {
while (\$b != 0)
list(\$a, \$b) = array(\$b, \$a%\$b);
return \$a;
}
```

### Seed7

```const func integer: gcd (in var integer: a, in var integer: b) is func
result
var integer: result is 0;
local
var integer: help is 0;
begin
while a <> 0 do
help := b rem a;
b := a;
a := help;
end while;
result := b;
end func;
```

### Common Lisp

Recursive version:

```;;; Common Lisp already includes a function which does this, called
;;; GCD.
;;; Tail recursive (remember that tail-recursive optimization is
;;; usually off by default in most CL compilers and interpreters)
(defun greatest-common-divisor (a b)
(if (zerop b)
a
(greatest-common-divisor b (mod a b))))
```

Iterative version:

```;;; Common Lisp already includes a function which does this, called
;;; GCD.
(defun greatest-common-divisor (a b)
(do ()
((zerop b) a)
(psetf a b b (mod a b))))
```