Logo

Programming-Idioms

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.

int gcd(int a, int b)
{
  while (b != 0)
  {
    int t = b;
    b = a % t;
    a = t;
  }
  return a;
}
int gcd(int a, int b)
{
  if (b == 0) 
    return a;
  else 
    return gcd(b, 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_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);
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)
New implementation...
< > ⌨
deleplace 
int gcd(int a, int b)
{
  while (b != 0)
  {
    int t = b;
    b = a % t;
    a = t;
  }
  return a;
}
int gcd(int a, int b)
{
  if (b == 0) 
    return a;
  else 
    return gcd(b, a % b);
}
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);
}
auto x = std::gcd(a, b);
x = gcd(a, b);
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)
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)
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)
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);
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;

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)
let x = a.gcd(&b);
Dim x = BigInteger.GreatestCommonDivisor(a, b)