This language bar is your friend. Select your favorite languages!

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.

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);
import std.numeric: gcd;
x = gcd(a, b);
int gcd(int a, int b) {
  while (b != 0) {
    var t = b;
    b = a % t;
    a = t;
  }
  return a;
}
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)
import "math/big"
x.GCD(nil, nil, a, b)
x = gcd a b
-1
import java.math.BigInteger;
BigInteger x = a.gcd(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;
from fractions import gcd
x = gcd(a, b)
x = a.gcd(b)
extern crate num;

use num::Integer;
use num::bigint::BigInt;
let x = a.gcd(&b);

Do you know the best way to do this in your language ?
New implementation...

Idiom created by

deleplace

Related idioms