# Idiom #74 Compute GCD

Compute the greatest common divisor x of big integers a and b. Use an integer type able to handle huge numbers.

``x = a.gcd(b)``
``#include <gmp.h>``
``````mpz_t _a, _b, _x;
mpz_init_set_str(_a, "123456789", 10);
mpz_init_set_str(_b, "987654321", 10);
mpz_init(_x);

mpz_gcd(_x, _a, _b);
gmp_printf("%Zd\n", _x);``````
``````(defn gcd [a b]
(if (zero? b)
a
(recur b (mod a b))))``````
``````unsigned long long int GCD(unsigned long long int a, unsigned long long int b)
{
unsigned long long int c=a%b;
if(c==0)
return b;
return GCD(b, c);
}``````
``#include <numeric>``
``auto x = std::gcd(a, b);``
``````int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}``````
``````int gcd(int a, int b)
{
while (b != 0)
{
int t = b;
b = a % t;
a = t;
}
return a;
}``````
``import std.numeric: gcd;``
``x = gcd(a, b);``
``import std.bigint;``
``````BigInt gcd(in BigInt x, in BigInt y) pure {
if (y == 0)
return x;
return gcd(y, x%y);
}

gcd(a, b);``````
``````int gcd(int a, int b) {
while (b != 0) {
var t = b;
b = a % t;
a = t;
}
return a;
}``````
``x = a.gcd(b);``
``````defmodule Gcd do
def gcd(x, 0), do: x
def gcd(x, y), do: gcd(y, rem(x,y))
end

x = Gcd.gcd(a, b)``````
``x = Integer.gcd(a, b)``
``````use,intrinsic : iso_fortran_env, only : int64
``````
``````function gcd(m,n) result(answer)
implicit none
integer(kind=int64),intent(in)  :: m, n
ifirst=iabs(m)
else
do
if(irest == 0)  exit
enddo
endif
end function gcd
``````
``import "math/big"``
``x.GCD(nil, nil, a, b)``
``````x = gcd a b
``````
``````gcd a b
|   a==b =a
|   a>b = gcd(a-b) b
|   otherwise = gcd a (b-a)``````
``````gcd x y =  gcd' (abs x) (abs y)
where
gcd' a 0  =  a
gcd' a b  =  gcd' b (a `rem` b)``````
``const gcd = (a, b) => b === 0 ? a : gcd (b, a % b)``
``import java.math.BigInteger;``
``BigInteger x = a.gcd(b);``
``````function gcd(x, y)
if (y == 0) then
return x
else
return gcd(y, x%y)
end
end``````
``````function gcd(a, b)
return b==0 and a or gcd(b,a%b)
end``````
``extension=gmp``
``\$x = gmp_gcd(\$a, \$b);``
``````function GCD(a,b:int64):int64;

var t:int64;

begin
while b <> 0 do
begin
t := b;
b := a mod b;
a := t;
end;
result := a;
end;
``````
``use bigint;``
``````sub gcd {
my (\$A, \$B) = @_;
return 0 == \$B
? \$A
: gcd(\$B, \$A % \$B);
}
``````
``import math``
``x = math.gcd(a, b)``
``from fractions import gcd``
``x = gcd(a, b)``
``````extern crate num;

use num::Integer;
use num::bigint::BigInt;``````
``let x = a.gcd(&b);``
``Imports System.Numerics``
``Dim x = BigInteger.GreatestCommonDivisor(a, b)	``

deleplace