Logo

Programming-Idioms

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

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations 
#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);
x = a.gcd(b);
int gcd(int a, int b) {
  while (b != 0) {
    var t = b;
    b = a % t;
    a = t;
  }
  return a;
}
x = Integer.gcd(a, 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)
use,intrinsic : iso_fortran_env, only : int64

function gcd(m,n) result(answer)
implicit none
integer(kind=int64),intent(in)  :: m, n
integer(kind=int64)             :: answer,irest,ifirst
   ifirst=iabs(m)
   answer=iabs(n)
   if(answer.eq.0)then
      answer=ifirst
   else
      do
         irest = mod(ifirst,answer)
         if(irest == 0)  exit
         ifirst = answer
         answer = irest
      enddo
      answer= iabs(answer)
   endif
end function gcd

import "math/big"
x.GCD(nil, nil, a, b)
gcd a b
    |   a==b =a
    |   a>b = gcd(a-b) b
    |   otherwise = gcd a (b-a)
x = gcd a b

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(a, b)
	return b==0 and a or gcd(b,a%b)
end
function gcd(x, y)
	if (y == 0) then
		return x
	else 
		return gcd(y, x%y)
	end
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)
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)

Preview