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.

defmodule Gcd do
  def gcd(x, 0), do: x
  def gcd(x, y), do: gcd(y, rem(x,y))

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

mpz_gcd(_x, _a, _b);
gmp_printf("%Zd\n", _x);
(defn gcd [a b]
  (if (zero? b)
    (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;
        return b;
    return GCD(b, c);
int gcd(int a, int b)
  if (b == 0) 
    return a;
    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;
import "math/big"
x.GCD(nil, nil, a, b)
x = gcd a b
const gcd = (a, b) => b === 0 ? a : gcd (b, a % b)
import java.math.BigInteger;
BigInteger x = a.gcd(b);
$x = gmp_gcd($a, $b);
function GCD(a,b:int64):int64;

var t:int64;

  while b <> 0 do
       t := b;
       b := a mod b;
       a := t;
    result := a;
use bigint;
sub gcd {
    my ($A, $B) = @_;
    return 0 == $B
        ? $A
        : gcd($B, $A % $B);
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);
Imports System.Numerics
Dim x = BigInteger.GreatestCommonDivisor(a, b)	

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

Idiom created by


Related idioms