Greatest common divisor: Difference between revisions

{{trans|Python}}

 

L v != 0

(u, v) = (v, u % v)

print(gcd(-6, 9))

print(gcd(8, 45))

 

{{out}}

For maximum compatibility, this program uses only the basic instruction set (S/360)

with 2 ASSIST macros (XDECO,XPRNT).

GCD CSECT

USING GCD,R15 use calling register

XDEC DS CL12 temp for edit

YREGS

{{out}}

<pre>

gcd( 1071, 1029)= 21

</pre>

 

=={{header|8th}}==

dup 0 n:= if drop ;; then

tuck \ b a b

 

bye

{{out}}

<pre>GCD of 5 and 100 = 5

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program calPgcd64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

=={{header|ACL2}}==

 

(defun gcd$ (x y)

nil)

((zp y) x)

 

=={{header|Action!}}==

CARD tmp

 

Test(123,1)

Test(0,0)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Greatest_common_divisor.png Screenshot from Atari 8-bit computer]

 

=={{header|ActionScript}}==

function gcd(a:int,b:int):int

{

}

return a;

 

=={{header|Ada}}==

 

procedure Gcd_Test is

Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100)));

Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23)));

 

Output:

 

=={{header|Aime}}==

o_byte('\n');

o_integer(gcd(49865, 69811));

 

=={{header|ALGOL 60}}==

comment Greatest common divisor - algol 60;

outinteger(1,gcd(21,35))

end

{{Out}}

<pre>

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of FORMATted transput}}

IF a = 0 THEN

b

INT c = 49865, d = 69811;

printf(($x"The gcd of"g" and "g" is "gl$,c,d,gcd(c,d)))

Output:

<pre>

 

=={{header|ALGOL-M}}==

 

% RETURN P MOD Q %

COMMENT - EXERCISE THE FUNCTION;

 

 

{{out}}

</pre>

 

=={{header|ALGOL W}}==

% iterative Greatest Common Divisor routine %

integer procedure gcd ( integer value m, n ) ;

a := abs( m );

b := abs( n );

end gcd ;

 

write( gcd( -21, 35 ) );

 

=={{header|Alore}}==

 

while b != 0

a,b = b, a mod b

end

return Abs(a)

 

=={{header|AntLang}}==

AntLang has a built-in gcd function.

 

It is not recommended, but possible to implement it on your own.

 

=={{header|APL}}==

By recursion:

 

on gcd(a, b)

if b ≠ 0 then

end if

end gcd

 

And just for the sake of it, the same thing iteratively:

 

repeat until (b = 0)

set x to a

if (a < 0) then return -a

return a

 

=={{header|Arendelle}}==

<pre>&lt; a , b &gt;

 

=={{header|Arturo}}==

 

{{out}}

{{works with|ATS|Postiats 0.4.1}}

 

 

(*

 

https://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&oldid=1072393147

 

 

The implementations shown here require the GCC builtin functions

that supports those functions, you are fine. Otherwise, one could

easily substitute other C code.

 

*)

(********************************************************************)

(* *)

(* *)

 

 

 

 

 

let

 

in

else

end

 

let

in

end

 

(********************************************************************)

(* *)

(* *)

 

unsigned integers. *)

extern fun {tk : tkind}

g0uint_gcd_stein (u, v) =

let

typedef t = g0uint tk

 

(* Use this macro to fake proof that an int is non-negative. *)

macdef nonneg (n) = $UNSAFE.cast{intGte 0} ,(n)

 

fun {tk : tkind}

let

in

else

end

 

val y = (v >> nonneg n)

 

val x_odd = (x >> nonneg (ctz x))

 

in

(z << nonneg n)

end

in

if iseqz u then

v

else

u_and_v_both_positive (u, v)

assertloc (gcd (~10, 0) = gcd (0U, 10U));

assertloc (gcd (~6L, ~9L) = 3UL);

end

 

 

=={{header|AutoHotkey}}==

Contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276379.html#276379 forum]

Return b=0 ? Abs(a) : Gcd(b,mod(a,b))

Significantly faster than recursion:

while b

b := Mod(a | 0x0, a := b)

return a

 

=={{header|AutoIt}}==

_GCD(18, 12)

_GCD(1071, 1029)

WEnd

EndFunc ;==>_GCD

 

Output: <pre>GCD of 18 : 12 = 6

=={{header|AWK}}==

The following scriptlet defines the gcd() function, then reads pairs of numbers from stdin, and reports their gcd on stdout.

12 16

4

11

45 67

 

=={{header|Axe}}==

r₁→A

r₂→B

Return

End

 

=={{header|BASIC}}==

 

{{trans|FreeBASIC}}

function gcdI(x, y)

while y

print : print "GCD(";a;", ";b;") = "; gcdI(a, b)

print : print "GCD(";a;", 111) = "; gcdI(a, 111)

{{out}}

<pre>

</pre>

 

function gcdp(a, b)

if b = 0 then return a

return gcdp(abs(a), abs(b))

end function

 

 

=={{header|Batch File}}==

Recursive method

@echo off

:gcd

echo Syntax:

echo GCD {a} {b}

 

=={{header|Bc}}==

 

Utility functions:

{

if ( a % 2 == 0 ) {

return(a);

}

 

'''Iterative (Euclid)'''

{

while(v) {

}

return(abs(u));

 

'''Recursive'''

 

{

if (v) {

return (abs(u));

}

 

'''Iterative (Binary)'''

 

{

u = abs(u);

}

return (u * k);

 

=={{header|BCPL}}==

 

let gcd(m,n) = n=0 -> m, gcd(n, m rem n)

show(1071,1029)

show(3528,3780)

{{out}}

<pre>gcd(18, 12) = 6

 

=={{header|Befunge}}==

 

=={{header|BQN}}==

 

Example:

<pre>7</pre>

 

=={{header|Bracmat}}==

Bracmat uses the Euclidean algorithm to simplify fractions. The <code>den</code> function extracts the denominator from a fraction.

Example:

<pre>{?} gcd$(49865.69811)

{!} 9973</pre>

 

=={{header|C}}==

===Iterative Euclid algorithm===

gcd_iter(int u, int v) {

if (u < 0) u = -u;

if (v) while ((u %= v) && (v %= u));

return (u + v);

 

===Recursive Euclid algorithm===

return (v != 0)?gcd(v, u%v):u;

 

===Iterative binary algorithm===

int t, k;

 

 

k = 1;

u >>= 1; v >>= 1;

k <<= 1;

t = (u & 1) ? -v : u;

while (t) {

t >>= 1;

 

}

return u * k;

 

=={{header|c sharp|C#}}==

===Iterative===

static void Main()

{

return a;

}

 

Example output:

</pre>

===Recursive===

static void Main(string[] args)

{

return b==0 ? a : gcd(b, a % b);

}

 

Example output:

 

=={{header|C++}}==

#include <numeric>

 

int main() {

std::cout << "The greatest common divisor of 12 and 18 is " << std::gcd(12, 18) << " !\n";

 

{{libheader|Boost}}

#include <iostream>

 

int main() {

std::cout << "The greatest common divisor of 12 and 18 is " << boost::math::gcd(12, 18) << "!\n";

 

{{out}}

===Euclid's Algorithm===

 

"(gcd a b) computes the greatest common divisor of a and b."

[a b]

(if (zero? b)

a

 

That <code>recur</code> call is the same as <code>(gcd b (mod a b))</code>, but makes use of Clojure's explicit tail call optimization.

This can be easily extended to work with variadic arguments:

 

"greatest common divisor of a list of numbers"

[& lst]

(reduce gcd

 

=== Stein's Algorithm (Binary GCD) ===

 

(cond

(zero? a) b

(and (even? a) (odd? b)) (recur (unsigned-bit-shift-right a 1) b)

(and (odd? a) (even? b)) (recur a (unsigned-bit-shift-right b 1))

 

=={{header|CLU}}==

while b~=0 do

a, b := b, a//b

|| int$unparse(gcd(as[i], bs[i])))

end

{{out}}

<pre>gcd(18, 12) = 6

 

=={{header|COBOL}}==

PROGRAM-ID. GCD.

 

END-PERFORM

DISPLAY "The gcd is " A

 

=={{header|Cobra}}==

 

class Rosetta

def gcd(u as number, v as number) as number

print "gcd of [96] and [27] is [.gcd(27, 96)]"

print "gcd of [51] and [34] is [.gcd(34, 51)]"

 

Output:

 

Simple recursion

gcd = (x, y) ->

if y == 0 then x else gcd y, x % y

 

Since JS has no TCO, here's a version with no recursion

gcd = (x, y) ->

[1..(Math.min x, y)].reduce (acc, v) ->

if x % v == 0 and y % v == 0 then v else acc

 

=={{header|Common Lisp}}==

Common Lisp provides a ''gcd'' function.

 

 

Here is an implementation using the do macro. We call the function <code>gcd*</code> so as not to conflict with <code>common-lisp:gcd</code>.

 

(do () ((zerop b) (abs a))

 

Here is a tail-recursive implementation.

 

(if (zerop b)

a

 

The last implementation is based on the loop macro.

 

(loop for x = a then y

and y = b then (mod x y)

until (zerop y)

 

=={{header|Component Pascal}}==

BlackBox Component Builder

MODULE Operations;

IMPORT StdLog,Args,Strings;

 

END Operations.

Execute:<br/>

^Q Operations.DoGcd 12 8 ~<br/>

 

=={{header|D}}==

 

long myGCD(in long x, in long y) pure nothrow @nogc {

gcd(15, 10).writeln; // From Phobos.

myGCD(15, 10).writeln;

{{out}}

<pre>5

 

=={{header|Dc}}==

This code assumes that there are two integers on the stack.

<pre>dc -e'28 24 [dSa%Lard0<G]dsGx+ p'</pre>

 

=={{header|Draco}}==

word t;

while n ~= 0 do

show(1071, 1029);

show(3528, 3780)

{{out}}

<pre>gcd(18, 12) = 6

gcd(1071, 1029) = 21

gcd(3528, 3780) = 252</pre>

 

=={{header|DWScript}}==

Output:

<pre>21</pre>

{{trans|Go}}

 

func bgcd(a, b, res) {

if a == b {

return bgcd(a, b, 1)

}

var testdata = [

]

for v in testdata {

 

{{out}}

{{trans|Python}}

 

while (v != 0) {

def r := u %% v

}

return u.abs()

 

=={{header|EasyLang}}==

 

.

 

=={{header|EDSAC order code}}==

The EDSAC had no division instruction,

so the GCD routine below has to include its own code for division.

[Greatest common divisor for Rosetta Code.

Program for EDSAC, Initial Orders 2.]

E 14 Z [define entry point]

P F [acc = 0 on entry]

{{out}}

<pre>

{{trans|D}}

 

class

APPLICATION

 

end

 

=={{header|Elena}}==

{{trans|C#}}

ELENA 4.x :

import extensions;

printGCD(36,19);

printGCD(36,33);

{{out}}

<pre>

 

=={{header|Elixir}}==

def gcd(a,0), do: abs(a)

def gcd(a,b), do: gcd(b, rem(a,b))

 

IO.puts RC.gcd(1071, 1029)

 

{{out}}

</pre>

 

 

(cond

((< a b) (gcd a (- b a)))

((> a b) (gcd (- a b) b))

 

=={{header|Erlang}}==

 

-module(gcd).

-export([main/0]).

gcd(A, 0) -> A;

 

{{out}}

<pre>4

=={{header|ERRE}}==

This is a iterative version.

PROGRAM EUCLIDE

! calculate G.C.D. between two integer numbers

PRINT("G.C.D. between";J%;"and";K%;"is";MCD%)

END PROGRAM

{{out}}

Input two numbers : ? 112,44

G.C.D. between 112 and 44 is 4

 

=={{header|Euler Math Toolbox}}==

Non-recursive version in Euler Math Toolbox. Note, that there is a built-in command.

 

>ggt(123456795,1234567851)

33

>myggt(123456795,1234567851)

33

 

=={{header|Euphoria}}==

{{trans|C/C++}}

===Iterative Euclid algorithm===

integer t

while v do

return u

end if

 

===Recursive Euclid algorithm===

if v then

return gcd(v, remainder(u, v))

return u

end if

 

===Iterative binary algorithm===

integer t, k

if u < 0 then -- abs(u)

end while

return u * k

 

=={{header|Excel}}==

Excel's GCD can handle multiple values. Type in a cell:

{{Out|Sample Output}}

This will get the GCD of the first 5 cells of the first row.

 

=={{header|Ezhil}}==

## இந்த நிரல் இரு எண்களுக்கு இடையிலான மீச்சிறு பொது மடங்கு (LCM), மீப்பெரு பொது வகுத்தி (GCD) என்ன என்று கணக்கிடும்

 

 

பதிப்பி "நீங்கள் தந்த இரு எண்களின் மீபொவ (மீப்பெரு பொது வகுத்தி, GCD) = ", மீபொவ(அ, ஆ)

 

=={{header|F_Sharp|F#}}==

let rec gcd a b =

if b = 0

>gcd 400 600

 

=={{header|Factor}}==

[ abs ] [

[ nip ] [ mod ] 2bi gcd

 

=={{header|FALSE}}==

 

=={{header|Fantom}}==

 

class Main

{

}

}

 

=={{header|Fermat}}==

 

=={{header|Forth}}==

 

=={{header|Fortran}}==

{{works with|Fortran|95 and later}}

===Recursive Euclid algorithm===

integer :: gcd

integer, intent(in) :: u, v

gcd = v

end if

 

===Iterative Euclid algorithm===

integer, intent(out) :: value

integer, intent(inout) :: u, v

enddo

value = abs(u)

 

A different version, and implemented as function

 

integer :: gcd

integer, intent(in) :: v, t

end do

gcd = b ! abs(b)

 

===Iterative binary algorithm===

integer, intent(out) :: value

integer, intent(inout) :: u, v

enddo

value = u * k

 

===Notes on performance===

<tt>gcd_bin(40902, 24140)</tt> takes us about '''2.5''' µsec

 

 

 

 

 

 

 

 

 

 

 

{{out}}

 

 

=={{header|Frege}}==

 

pure native parseInt java.lang.Integer.parseInt :: String -> Int

(a:b:_) = args

println $ gcd' (parseInt a) (parseInt b)

 

=={{header|Frink}}==

Frink has a builtin <CODE>gcd[x,y]</CODE> function that returns the GCD of two integers (which can be arbitrarily large.)

println[gcd[12345,98765]]

 

=={{header|FunL}}==

FunL has pre-defined function <code>gcd</code> in module <code>integers</code> defined as:

 

gcd( 0, 0 ) = error( 'integers.gcd: gcd( 0, 0 ) is undefined' )

gcd( a, b ) =

_gcd( a, b ) = _gcd( b, a%b )

 

 

=={{header|FutureBasic}}==

 

 

 

=={{header|GAP}}==

GcdInt(35, 42);

# 7

 

GcdInteger(35, 42);

 

=={{header|Genyris}}==

===Recursive===

u = (abs u)

v = (abs v)

cond

(equal? v 0) u

 

===Iterative===

u = (abs u)

v = (abs v)

u = v

v = tmp

 

=={{header|GML}}==

var n,m,r;

n = max(argument0,argument1);

}

return a;

 

=={{header|gnuplot}}==

Example:

Output:

 

=={{header|Go}}==

===Binary Euclidian===

 

import "fmt"

}

}

{{out|Output for Binary Euclidian algorithm}}

<pre>

</pre>

===Iterative===

 

import "fmt"

fmt.Println(gcd(49865, 69811))

}

===Builtin===

(This is just a wrapper for <tt>big.GCD</tt>)

 

import (

fmt.Println(gcd(33, 77))

fmt.Println(gcd(49865, 69811))

{{out|Output in either case}}

<pre>

 

=={{header|Golfscript}}==

{{out}}

<pre>

=={{header|Groovy}}==

===Recursive===

 

===Iterative===

 

Test program:

println "gcd(28, 0) = ${gcdR(28, 0)} == ${gcdI(28, 0)}"

println "gcd(0, 28) = ${gcdR(0, 28)} == ${gcdI(0, 28)}"

println "gcd(28, 70) = ${gcdR(28, 70)} == ${gcdI(28, 70)}"

println "gcd(800, 70) = ${gcdR(800, 70)} == ${gcdI(800, 70)}"

 

Output:

gcd(800, 70) = 10 == 10

gcd(27, -70) = 1 == 1</pre>

 

=={{header|Haskell}}==

That is already available as the function ''gcd'' in the Prelude. Here's the implementation, with one name adjusted to avoid a Wiki formatting glitch:

 

gcd x y = gcd_ (abs x) (abs y)

where

gcd_ a 0 = a

 

=={{header|HicEst}}==

IF(b == 0) THEN

gcd = ABS(a)

ENDDO

ENDIF

 

=={{header|Icon}} and {{header|Unicon}}==

procedure main(args)

write(gcd(arg[1], arg[2])) | "Usage: gcd n m")

 

{{libheader|Icon Programming Library}} [http://www.cs.arizona.edu/icon/library/procs/numbers.htm numbers] implements this as:

 

local r

 

j := r

}

 

=={{header|J}}==

 

For example:

 

 

Note that <code>+.</code> is a single, two character token. GCD is a primitive in J (and anyone that has studied the right kind of mathematics should instantly recognize why the same operation is used for both GCD and OR -- among other things, GCD and boolean OR both have the same identity element: 0, and of course they produce the same numeric results on the same arguments (when we are allowed to use the usual 1 bit implementation of 0 and 1 for false and true) - more than that, though, GCD corresponds to George Boole's original "Boolean Algebra" (as it was later called). The redefinition of "Boolean algebra" to include logical negation came much later, in the 20th century).

gcd could also be defined recursively, if you do not mind a little inefficiency:

 

 

=={{header|Java}}==

===Iterative===

long factor= Math.min(a, b);

for(long loop= factor;loop > 1;loop--){

}

return 1;

 

===Iterative Euclid's Algorithm===

public static int gcd(int a, int b) //valid for positive integers.

{

return a;

}

 

===Optimized Iterative===

static int gcd(int a,int b)

{

return 1;

}

 

===Iterative binary algorithm===

{{trans|C/C++}}

long t, k;

}

return u * k;

===Recursive===

if(a == 0) return b;

if(b == 0) return a;

if(a > b) return gcd(b, a % b);

return gcd(a, b % a);

===Built-in===

 

public static long gcd(long a, long b){

return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();

 

=={{header|JavaScript}}==

Iterative implementation

a = Math.abs(a);

b = Math.abs(b);

if (b === 0) { return a; }

}

 

Recursive.

return b ? gcd_rec(b, a % b) : Math.abs(a);

 

Implementation that works on an array of integers.

var i, y,

n = arr.length,

//For example:

GCD([57,0,-45,-18,90,447]); //=> 3

 

=={{header|Joy}}==

 

=={{header|jq}}==

if b == 0 then a

else recursive_gcd(b; a % b)

# The subfunction expects [a,b] as input

# i.e. a ~ .[0] and b ~ .[1]

else [.[1], .[0] % .[1]] | rgcd

end;

 

=={{header|Julia}}==

1</pre>

The actual implementation of this function in Julia 0.2's standard library is reproduced here:

neg = a < 0

while b != 0

g = abs(a)

neg ? -g : g

(For arbitrary-precision integers, Julia calls a different implementation from the GMP library.)

 

=={{header|K}}==

 

=={{header|Klong}}==

 

=={{header|Kotlin}}==

Recursive one line solution:

 

=={{header|LabVIEW}}==

 

=={{header|Lambdatalk}}==

 

{def gcd

{S.map {GCD 123} {S.serie 1 30}}

-> 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3

 

=={{header|LFE}}==

{{trans|Clojure}}

 

> (defun gcd

"Get the greatest common divisor."

((a 0) a)

((a b) (gcd b (rem a b))))

 

Usage:

17

</pre>

 

=={{header|Limbo}}==

{

if(y == 0)

return gcd(y, x % y);

}

 

=={{header|LiveCode}}==

repeat until y = 0

put x mod y into z

end repeat

return x

 

=={{header|Logo}}==

if :b = 0 [output :a]

output gcd :b modulo :a :b

 

=={{header|LOLCODE}}==

 

HOW IZ I gcd YR a AN YR b

VISIBLE I IZ gcd YR 40902 AN YR 24140 MKAY

 

[https://tio.run/##jVJNU8IwFDw3v2KPOoNOwV48Oal8NAMlTpuK5ZZARMcydVrw79ekrUhlRHNJ3kt2377Ny/Jsla91VQWUoX99Q0jAF2BLMGxWa6QRJOjc7oo4EhF8NplE4OMm/xDxYTIVh/iqD8AXC0CqMs/2O40Pme018mdI4qhjAvWDQP1FYBT4XASI6ShsyqkeOKJZekccJ6X2ZA7OmCfzYS3dRJzdn8Dc8zB1ClP/gMlfYF3HDpLRrLrXrXzTKPeFNm9eS@xeNDJZbHRh276QPajLTk2GgMag2OntO5hY1rXr77Haa5vtVSuIOCwEqz8xy3ObPcFbmEWFfPitlDSULdMZM46Ude1o/DDVeSIE/RIAwsZIDFeKmBPyyGLmz0Zm4szYtUPnubfuoB28gdf3XIRTmhIyFcGTn46q6hM Try it online!]

 

=={{header|LSE}}==

** MÉTHODE D'EUCLIDE POUR TROUVER LE PLUS GRAND DIVISEUR COMMUN D'UN

** NUMÉRATEUR ET D'UN DÉNOMINATEUR.

&DEMO(6144,8192)

&DEMO(100,5)

 

Resultats:

=={{header|Lua}}==

{{trans|C}}

if b ~= 0 then

return gcd(b, a % b)

demo(100, 5)

demo(5, 100)

 

Output:

 

Faster iterative solution of Euclid:

while b~=0 do

a,b=b,a%b

return math.abs(a)

end

 

=={{header|Lucid}}==

===dataflow algorithm===

z = [% n, m %] fby if x > y then [% x - y, y %] else [% x, y - x%] fi;

x = hd(z);

y = hd(tl(z));

gcd(n, m) = (x asa x*y eq 0) fby eod;

 

=={{header|Luck}}==

if a==0 then b

else if b==0 then a

else if a>b then gcd(b, a % b)

else gcd(a, b % a)

 

=={{header|M2000 Interpreter}}==

gcd=lambda (u as long, v as long) -> {

=if(v=0&->abs(u), lambda(v, u mod v))

CheckGCD gcd

CheckGCD gcd_Iterative

 

=={{header|Maple}}==

To compute the greatest common divisor of two integers in Maple, use the procedure igcd.

 

 

For example,

> igcd( 24, 15 );

3

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

 

=={{header|MATLAB}}==

 

=={{header|Maxima}}==

gcd2(a, b) := block([a: abs(a), b: abs(b)], while b # 0 do [a, b]: [b, mod(a, b)], a)$

 

/* both will return 2^97 * 3^48 */

gcd(100!, 6^100), factor;

 

=={{header|MAXScript}}==

===Iterative Euclid algorithm===

(

while b > 0 do

)

abs a

 

===Recursive Euclid algorithm===

(

if b > 0 then gcdRec b (mod a b) else abs a

 

=={{header|Mercury}}==

===Recursive Euclid algorithm===

 

:- interface.

 

:- pragma memo(gcd/2).

 

An example console program to demonstrate the gcd module:

 

:- interface.

Fmt = integer.to_string,

GCD = gcd(A, B),

 

Example output:

 

=={{header|MINIL}}==

00 0E GCD: ENT R0

01 1E ENT R1

0A 1D Stop: DEC R1

0B C2 JNZ Again

 

=={{header|MiniScript}}==

Using an iterative Euclidean algorithm:

while b

temp = b

end function

 

{{output}}

<pre>6</pre>

 

=={{header|MIPS Assembly}}==

# a0 and a1 are the two integer parameters

# return value is in v0

done:

move $v0, $t0

 

=={{header|МК-61/52}}==

=={{header|ML}}==

==={{header|mLite}}===

| (0, b) = b

| (a, b) where (a < b)

| (a, b) = gcd (b, a rem b)

 

 

 

=={{header|Modula-2}}==

 

FROM InOut IMPORT ReadCard, WriteCard, WriteLn, WriteString, WriteBf;

WriteString ("u ="); WriteCard (u, 6); WriteLn;

WriteString ("v ="); WriteCard (v , 6); WriteLn

Producing the output

x = 12

y = 20

kgV = 10455

u = 13773

 

=={{header|Modula-3}}==

 

IMPORT IO, Fmt;

IO.Put("GCD of 5, 100 is " & Fmt.Int(GCD(5, 100)) & "\n");

IO.Put("GCD of 7, 23 is " & Fmt.Int(GCD(7, 23)) & "\n");

 

Output:

GCD of 7, 23 is 1

</pre>

 

=={{header|MUMPS}}==

GCD(A,B)

QUIT:((A/1)'=(A\1))!((B/1)'=(B\1)) 0

IF B'=0

FOR SET T=A#B,A=B,B=T QUIT:B=0 ;ARGUEMENTLESS FOR NEEDS TWO SPACES

 

Ouput:

=={{header|MySQL}}==

 

DROP FUNCTION IF EXISTS gcd;

DELIMITER |

 

SELECT gcd(12345, 9876);

 

+------------------+

{{trans|Java}}

===Iterative===

factor = a.min(b)

 

 

return 1

 

===Iterative Euclid's Method===

while b > 0

c = a % b

end

return a

 

=={{header|NetRexx}}==

options replace format comments java crossref symbols nobinary

 

return

 

-- Euclid's algorithm - iterative implementation

method gcdEucidI(a_, b_) public static

return a_

 

-- Euclid's algorithm - recursive implementation

method gcdEucidR(a_, b_) public static

return a_

 

method runSample(arg) private static

-- pairs of numbers, each number in the pair separated by a colon, each pair separated by a comma

return

 

method showResults(stem, title) public static

say

return

 

method verifyResults(stem1, stem2) public static returns boolean

if stem1[0] \= stem2[0] then signal BadArgumentException

end i_

return verified

{{out}}

<pre>

 

=={{header|NewLISP}}==

 

=={{header|Nial}}==

Nial provides gcd in the standard lib.

|gcd 6 4

 

defining it for arrays

# one is termination condition

red is cull filter (0 unequal) link [mod [rest, first] , first]

one is or [= [1 first, tally], > [2 first, first]]

 

Using it

 

=={{header|Nim}}==

{{trans|Pascal}}

===Recursive Euclid algorithm===

if u mod v != 0:

result = gcd_recursive(v, u mod v)

import strformat

let (x, y) = (49865, 69811)

 

{{out}}

 

===Iterative Euclid algorithm===

var u = u

var v = v

import strformat

let (x, y) = (49865, 69811)

 

{{out}}

 

===Iterative binary algorithm===

 

func gcd_binary*(u, v: int64): int64 =

import strformat

let (x, y) = (49865, 69811)

{{out}}

<pre>gcd(49865, 69811) = 9973</pre>

=={{header|Oberon-2}}==

Works with oo2c version 2

MODULE GCD;

(* Greatest Common Divisor *)

Out.String("GCD of 40902 and 24140 : ");Out.LongInt(Gcd(40902,24140),4);Out.Ln

END GCD.

Output:<br/>

<pre>

 

=={{header|Objeck}}==

bundle Default {

class GDC {

}

}

 

=={{header|OCaml}}==

 

=== Built-in ===

open Big_int;;

let gcd a b =

 

=={{header|Octave}}==

 

 

=={{header|Oforth}}==

 

gcd is already defined into Integer class :

 

Source of this method is (see Integer.of file) :

 

=={{header|Ol}}==

(print (gcd 1071 1029))

; ==> 21

 

=={{header|Order}}==

{{trans|bc}}

 

#define ORDER_PP_DEF_8gcd ORDER_PP_FN( \

8fn(8U, 8V, \

8if(8isnt_0(8V), 8gcd(8V, 8remainder(8U, 8V)), 8U)))

 

=={{header|Oz}}==

fun {UnsafeGCD A B}

if B == 0 then

end

in

 

=={{header|PARI/GP}}==

 

[[PASCAL]]

===Recursive Euclid algorithm===

{{works with|Free Pascal|version 3.2.0 }}

PROGRAM EXRECURGCD.PAS;

 

END.

 

 

===Iterative Euclid algorithm===

var

t: longint;

end;

gcd_iterative := abs(u);

 

===Iterative binary algorithm===

var

t, k: longint;

gcd_binary := u * k;

end;

 

Demo program:

 

begin

writeln ('GCD(', 49865, ', ', 69811, '): ', gcd_iterative(49865, 69811), ' (iterative)');

writeln ('GCD(', 49865, ', ', 69811, '): ', gcd_recursive(49865, 69811), ' (recursive)');

writeln ('GCD(', 49865, ', ', 69811, '): ', gcd_binary (49865, 69811), ' (binary)');

Output:

<pre>GCD(49865, 69811): 9973 (iterative)

=={{header|Perl}}==

===Iterative Euclid algorithm===

my ($u, $v) = @_;

while ($v) {

}

return abs($u);

 

===Recursive Euclid algorithm===

my ($u, $v) = @_;

if ($v) {

return abs($u);

}

 

===Iterative binary algorithm===

my ($u, $v) = @_;

$u = abs($u);

}

return $u * $k;

 

===Modules===

All three modules will take large integers as input, e.g.

<tt>gcd("68095260063025322303723429387", "51306142182612010300800963053")</tt>. Other possibilities are Math::Cephes euclid, Math::GMPz gcd and gcd_ui.

use Math::Prime::Util "gcd";

$gcd = gcd(49865, 69811);

use Math::Pari "gcd";

$gcd = gcd(49865, 69811)->pari2iv

 

===Notes on performance===

use Math::BigInt;

use Math::Pari;

'gcd_pari' => sub { Math::Pari::gcd($u,$v)->pari2iv(); },

'gcd_mpu' => sub { Math::Prime::Util::gcd($u,$v); },

 

Output on 'Intel i3930k 4.2GHz' / Linux / Perl 5.20:

atom parameters allow greater precision, but any fractional parts are immediately and deliberately discarded.<br>

Actually, it is an autoinclude, reproduced below. The first parameter can be a sequence, in which case the second parameter (if provided) is ignored.

<span style="color: #008080;">function</span> <span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>

<span style="color: #004080;">atom</span> <span style="color: #000000;">t</span>

<span style="color: #008080;">return</span> <span style="color: #000000;">u</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

Sample results

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 0</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">24</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">112</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 8</span>

<span style="color: #000080;font-style:italic;">-- 10000000000000000000</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">({</span><span style="color: #000000;">57</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">45</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">90</span><span style="color: #0000FF;">,</span><span style="color: #000000;">447</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- 3</span>

 

=={{header|PHP}}==

 

===Iterative===

function gcdIter($n, $m) {

while(true) {

}

}

 

===Recursive===

function gcdRec($n, $m)

{

return abs($n);

}

 

=={{header|PicoLisp}}==

(until (=0 B)

(let M (% A B)

(setq A B B M) ) )

 

=={{header|PL/I}}==

GCD: procedure (a, b) returns (fixed binary (31)) recursive;

declare (a, b) fixed binary (31);

 

end GCD;

 

=={{header|Pop11}}==

===Built-in gcd===

 

Note: the last argument gives the number of other arguments (in

this case 2).

===Iterative Euclid algorithm===

lvars k , l, r = l;

abs(k) -> k;

endwhile;

k -> r;

 

=={{header|PostScript}}==

{{libheader|initlib}}

/gcd {

{

} loop

}.

With no external lib, recursive

/gcd {

dup 0 ne {

} { pop } ifelse

} def

 

=={{header|PowerShell}}==

===Recursive Euclid Algorithm===

{

if ($x -eq $y) { return $y }

}

return $b

 

or shorter (taken from Python implementation)

if ($y -eq 0) { $x } else { Get-GCD $y ($x%$y) }

 

===Iterative Euclid Algorithm===

 

based on Python implementation

Function Get-GCD( $x, $y ) {

while ($y -ne 0) {

[Math]::abs($x)

}

 

=={{header|Prolog}}==

===Recursive Euclid Algorithm===

gcd(0, X, X):- !.

gcd(X, Y, D):- X > Y, !, Z is X mod Y, gcd(Y, Z, D).

 

===Repeated Subtraction===

gcd(0, X, X):- !.

gcd(X, Y, D):- X =< Y, !, Z is Y - X, gcd(X, Z, D).

 

=={{header|Purity}}==

data Iterate = f => FoldNat <const id, g => $g . $f>

 

 

data gcd = Iterate (gcd => uncurry (step (curry $gcd)))

 

=={{header|Python}}==

===Built-in===

{{works with|Python|2.6+}}

 

{{Works with|Python|3.7}}

(Note that '''fractions.gcd''' is now deprecated in Python 3)

 

===Iterative Euclid algorithm===

while v:

u, v = v, u % v

 

===Recursive Euclid algorithm===

'''Interpreter:''' [[Python]] 2.5

 

===Tests===

===Iterative binary algorithm===

See [[The Art of Computer Programming]] by Knuth (Vol.2)

u, v = abs(u), abs(v) # u >= 0, v >= 0

if u < v:

v = -t

t = u - v

 

===Notes on performance===

 

<tt>gcd_bin(40902, 24140)</tt> takes us about '''41''' µsec

 

=={{header|Quackery}}==

[ [ dup while

tuck mod again ]

drop abs ] is gcd ( n n --> n )

 

=={{header|R}}==

Recursive:

ifelse(u %% v != 0, v %gcd% (u%%v), v)

Iterative:

while ( (c <- v%%t) != 0 ) {

v <- t

}

t

{{out}}

Same either way.

Racket provides a built-in gcd function. Here's a program that computes the gcd of 14 and 63:

 

 

 

Here's an explicit implementation. Note that since Racket is tail-calling, the memory behavior of this program is "loop-like", in the sense that this program will consume no more memory than a loop-based implementation.

 

 

;; given two nonnegative integers, produces their greatest

(* 3 3 7))

(check-equal? (gcd 0 14) 14)

 

=={{header|Raku}}==

 

===Iterative===

$a & $b == 0 and fail;

($a, $b) = ($b, $a % $b) while $b;

return abs $a;

 

===Recursive===

multi gcd (Int $a, 0) { abs $a }

 

===Concise===

 

===Actually, it's a built-in infix===

Because it's an infix, you can use it with various meta-operators:

@alist Zgcd @blist; # lazy zip with gcd

@alist Xgcd @blist; # lazy cross with gcd

 

=={{header|Rascal}}==

 

===Iterative Euclidean algorithm===

public int gcd_iterative(int a, b){

if(a == 0) return b;

return a;

}

An example:

rascal>gcd_iterative(1989, 867)

int: 51

 

===Recursive Euclidean algorithm===

public int gcd_recursive(int a, b){

return (b == 0) ? a : gcd_recursive(b, a%b);

}

An example:

rascal>gcd_recursive(1989, 867)

int: 51

 

=={{header|Raven}}==

===Recursive Euclidean algorithm===

$v 0 > if

$u $v % $v gcd

$u abs

 

{{out}}<pre>34</pre>

 

=={{header|REBOL}}==

{Returns the greatest common divisor of m and n.}

m [integer!]

]

m

 

=={{header|Retro}}==

This is from the math extensions library.

 

 

=={{header|REXX}}==

<br>argument(s), &nbsp; making it easier to use when computing Frobenius numbers &nbsp; (also known as &nbsp; ''postage stamp'' &nbsp; or &nbsp;

<br>''coin'' &nbsp; numbers).

numeric digits 2000 /*handle up to 2k decimal dig integers.*/

call gcd 0 0 ; call gcd 55 0 ; call gcd 0 66

 

say 'GCD (Greatest Common Divisor) of ' translate(space($),",",' ') " is " x

'''output'''

<pre>

===version 2===

Recursive function (as in PL/I):

/* REXX ***************************************************************

* using PL/I code extended to many arguments

Parse Arg a,b

if b = 0 then return abs(a)

Output:

<pre>

Considerably faster than version 1 (and version 2)

<br>See http://rosettacode.org/wiki/Least_common_multiple#REXX for reasoning.

x=abs(arg(1))

do j=2 to arg()

end

end

 

=={{header|Ring}}==

see gcd (24, 32)

func gcd gcd, b

end

return gcd