Logo

Programming-Idioms

  • Rust
  • Pascal
  • C++

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.

#include <numeric>
auto x = std::gcd(a, b);

C++17 or later

Uses the absolute values of a and b in calculations
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);
}

This implementation is the cleanest I know, but it is not meant for negative integers.
extern crate num;

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

Uses the num crate's Integer trait.
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;

Using the Euklid Algorithm
#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);
New implementation...
< > ⌨
deleplace 
auto x = std::gcd(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);
}
let 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;

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))))
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;
}
BigInt gcd(in BigInt x, in BigInt y) pure {
    if (y == 0)
        return x;
    return gcd(y, x%y);
}

gcd(a, b);
x = 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)
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

x.GCD(nil, nil, a, b)
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)
gcd a b
    |   a==b =a
    |   a>b = gcd(a-b) b
    |   otherwise = gcd a (b-a)
const gcd = (a, b) => b === 0 ? a : gcd (b, a % b)
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
$x = gmp_gcd($a, $b);
sub gcd {
    my ($A, $B) = @_;
    return 0 == $B
        ? $A
        : gcd($B, $A % $B);
}

x = math.gcd(a, b)
x = gcd(a, b)
x = a.gcd(b)
Dim x = BigInteger.GreatestCommonDivisor(a, b)