# Greatest Common Divisor

Your task is to compute the greatest common divisor (GCD) of two given integers in as few bytes of code as possible.

You may write a program or function, taking input and returning output via any of our accepted standard methods (including STDIN/STDOUT, function parameters/return values, command-line arguments, etc.).

Input will be two non-negative integers. You should be able to handle either the full range supported by your language's default integer type, or the range [0,255], whichever is greater. You are guaranteed that at least one of the inputs will be non-zero.

You are not allowed to use built-ins that compute either the GCD or the LCM (least common multiple).

Standard rules apply.

### Test Cases

0 2     => 2
6 0     => 6
30 42   => 6
15 14   => 1
7 7     => 7
69 25   => 1
21 12   => 3
169 123 => 1
20 142  => 2
101 202 => 101

• If we're allowing asm to have inputs in whatever registers are convenient, and the result in whatever reg is convenient, we should definitely be allowing functions, or even code fragments (i.e. just a function body). Making my answer a complete function would add about 4B with a register calling convention like MS's 32bit vectorcall (one xchg eax, one mov, and a ret), or more with a stack calling convention. Apr 8 '16 at 23:05
• @PeterCordes Sorry, I should have been more specific. You can totally just write the bear necessary code but if you would be so kind as to include a way to run said code it would be nice. Apr 9 '16 at 18:59
• So count just the gcd code, but provide the surrounding code so people can verify / experiment / improve? BTW, your test-cases with zero as one of the two inputs break our x86 machine code answers. div by zero raises a hardware exception. On Linux, your process gets a SIGFPE. Apr 9 '16 at 19:30
• @CodesInChaos Memory and time limitations are usually ignored as long as the algorithm itself can in principle handle all inputs. The rule is just meant to avoid people hardcoding arbitrary limits for loops that artificially limits the algorithm to a smaller range of inputs. I don't quite see how immutability comes into this? Apr 10 '16 at 14:10
• gcd(0,n) is error not n
– user58988
Mar 18 '19 at 12:33

# Oracle SQL 11.2, 104 118 bytes

SELECT MAX(:1+:2-LEVEL+1)FROM DUAL WHERE(MOD(:1,:1+:2-LEVEL+1)+MOD(:2,:1+:2-LEVEL+1))*:1*:2=0 CONNECT BY LEVEL<=:1+:2;


Fixed for input of 0

• Does not work correctly if one of inputs is zero. Apr 10 '16 at 14:05
• This should save you a few SELECT MAX(LEVEL)FROM DUAL WHERE MOD(:1,LEVEL)+MOD(:2,LEVEL)=0 CONNECT BY LEVEL<=:1+:2; Apr 10 '16 at 23:50

# ><>, 12+3 = 15 bytes

:?!\:}%
;n~/


Expects the input numbers to be present on the stack, so +3 bytes for the -v flag. Try it online!

Another implementation of the Euclidean algorithm.

# Maple, 77 75 bytes

if(min(a,b)=0,max(a,b),max(intersect(op(numtheory:-divisors~({a,b})))))


Usage:

> f:=(a,b)->ifelse(min(a,b)=0,max(a,b),max(intersect(op(numtheory:-divisors~({a,b})))));
> f(0,6);
6
> f(21,12);
3


This uses a Maple deprecated built-in for computing all of the factors for a and b. The updated built-in is NumberTheory:-Divisors.

# Java 8, 44 37 bytes

Here is a straight up, non-recursive (because of the lambda) Euclidean algorithm.

(x,y)->{while(y>0)y=x%(x=y);return x}


Update

• -7 [16-10-04] Simplified while condition

# PHP, 41 51 bytes

similar to my LCM answer:

for($d=1+$a=$argv[1];$argv[2]%--$d||$a%$d;);echo$d;


loop $d down from $argv[1] while $argv[1]/$d or $argv[2]/$d have a remainder.

## Racket 38 bytes

  (λ(a b)(if(> b 0)(f b(modulo a b))a))


Ungolfed:

(define f
(λ (a b)
(if (<= b 0)
a
(f b (modulo a b))
)))


Testing:

(f 0 2)
(f 6 0)
(f 30 42)
(f 15 14)
(f 7 7)
(f 69 25)
(f 21 12)
(f 169 123)
(f 20 142)
(f 101 202)


Output:

2
6
6
1
7
1
3
1
2
101

• Built-ins are disallowed in the challenge specification. Oct 4 '16 at 14:02
• I have corrected the answer.
– rnso
Oct 4 '16 at 16:32

## Logy, 64 23 bytes (non-competing)

f[X,Y]->Y<1&X|f[Y,X%Y];


Ungolfed:

gcd[X, Y] -> Y < 1 & X | gcd[Y, X%Y];


EDIT: Removed way too many bytes because there is no need for a full program

# Perl 5, 51 bytes

49bytes of code + 2 flags (-pa)

$b=pop@F;($_,$b)=(abs$_-$b,$_>$b?$b:$_)while$_-$b  Try it online! # Perl 5, 54 bytes sub g{my($a,$b)=@_;$a-$b?g(abs($a-$b),$a>$b?$b:$a):$a}


Try it online!

# Java, 38 bytes

f=(int a,b)->{return b==0?a:f(b,a%b);}

• Welcome to PPCG! Dec 18 '17 at 0:58
• @Ricker thanks :) (I'm assuming that stands for programming puzzles code golf) Dec 18 '17 at 1:45

# tinylisp, 44 bytes

(d G(q((a b)(i(l b a)(G b a)(i a(G(s b a)a)b


Defines a function G that takes two arguments. Try it online!

### Explanation

Since mod is not built into tinylisp, we use a subtraction-based algorithm instead.

(Glossary of tinylisp builtins used: d = def, q = quote, i = if, l = less-than, s = subtract)

• Define G (d G as a function that takes two arguments (q((a b)
• If the second argument is smaller (i(l b a) then recurse with the arguments swapped (G b a)
• Otherwise, if the first argument is nonzero (i a then recurse with the new arguments being (larger minus smaller) and (smaller) (G(s b a)a)
• Otherwise (the first argument is zero) return the second argument b

# Javascript, 21 bytes.

I think I'm doing this right, I'm still super new to Javascript.

g=a=>b=>b?g(b)(a%b):a

• That won't work. You define g as curried monads, yet use is as a dyadic function. Apr 7 '16 at 18:21
• @Dennis I think I just fixed it? Like I said, super new to JS. Apr 7 '16 at 18:22
• Yes, that works. For the record, g=(a,b)=>b?a:g(b,a%b) is equally short. Apr 7 '16 at 18:23
• @Dennis Ahhhh, that's what I was missing. I forgot the parens around the arguments and it was throwing syntax errors. Apr 7 '16 at 18:24
• Did you intend to put the ternary values the other way around? g=a=>b=>b?g(b)(a%b):a Apr 8 '16 at 3:39

# Japt, 18 bytes

wV Ä o a@!UuX «VuX


Brute force, tries every integer.

Try it online!

# Brachylog, 5 bytes

ḋˢ⊇ᵛ×


Try it online!

Takes input as a list through the input variable and outputs an integer through the output variable. If you use it as a generator, it actually generates all common divisors, it just does so largest first.

         The output is
×    the product of the elements of
⊇      the maximal sublist
ᵛ     which is shared by
ḋ        the prime factorization
ˢ       s of the elements of the input which have them.


# Add++, 26 bytes

D,g,@@#~,%A$p%+ L,MRBCþgbM  Try it online! Generates the range $$\1, 2, 3, ..., \max(a, b)$/extract_tex], then filters out elements that don't divide either $$\a$$/extract_tex] or $$\b\$$, Finally, we return the maximum value of the filtered elements. ## ARMv7 (OakSim), 28 bytes Hexdump: 0x00010000: 01 00 80 E0 00 10 81 E0 01 00 50 E1 01 00 40 C0 ..........P...@. 0x00010010: 00 10 41 B0 FB FF FF 1A 1E FF 2F E1 00 00 00 00 ..A......./.....  ## Explanation Callable function, expects the arguments in r0 and r1, output is in r0. Expects address of caller stored in lr. This is the standard method of procedure calling as per the ATPCS (ARM Thumb Procedure Call Standard). gcd: add r0, r0, r1 /* Make sure r0 is nonzero */ add r1, r1, r0 /* Make sure r1 is nonzero */ /* We're basically doing the inverse afterwards */ loop: /* main loop: */ cmp r0, r1 /* Compare r0 and r1 */ subgt r0, r0, r1 /* If r0 > r1: r0 = r0 - r1 */ sublt r1, r1, r0 /* If r0 < r1: r1 = r1 - r0 */ bne loop /* If r0 != r1: jump back to main loop */ bx lr /* return to caller */  ### Example call b caller /* jump to the caller */ gcd: /* omitted to save space */ caller: mov r0, 30 /* first operand = 30 */ mov r1, 42 /* second operand = 42 */ mov lr, pc /* link register = program counter */ b gcd /* branch to function */  # Forth (gforth), 37 34 bytes : f dup if tuck mod recurse then ;  Try it online! Same as the code below, but using recursion instead. Turns out that the combination if then recurse is shorter than begin while repeat by 3 chars, even though the word recurse looks quite bulky. ### Previous solution, 37 bytes : f begin dup while tuck mod repeat ;  Try it online! Input is two single-cell integers, output is one double-cell integer. ### How it works A "cell" means a space for one item on the stack. A double-cell integer in Forth takes two cells, where the most significant cell is on the top. For this challenge, the GCD of two single-cell integers always fits in a cell, so the upper cell is always 0. : f ( a b -- d ) \ Define a function f which takes two singles and gives a double begin \ Start a loop dup while \ While b is not zero... tuck \ Copy b under a ( stack: b a b ) and mod \ Calculate a%b ( stack: b a%b ) \ That is, change ( a b ) to ( b a%b ) repeat ; \ End loop \ The result is ( gcd 0 ) which is gcd in double-cell  # Scheme, 44 bytes (define(f a b)(if(= b 0)a(f b(modulo a b))))  Scheme is the future of code-golf. :) # RETURN, 16 bytes [[\¤÷%G][$?]=G  Try it here. Recursive operator implementation of Euclid's algorithm. Leaves result on top of stack. Usage: [[\¤÷%G][$$?]=G21 12G  # Explanation [ ]=G Define operator G$                Check if b is truthy
[     ][ ]?     Conditional
\¤               If so, create pattern [b a b] on stack
÷%             Mod top 2 items
G            Recurse
\         Otherwise, swap top 2 items


## Seriously, 23 bytes

,,;'XQ1╟";(%{}"f3δI£ƒkΣ


This makes use of the Quine command, which is currently the only sane way to do recursion.

Try it online!

Explanation:

,,;'XQ1╟";(%{}"f3δI£ƒkΣ
,,;                      get a and b inputs, duplicate b
'X                    push "x"
Q1╟                 push a list containing the program's source code as the singular element
";(%{}"f         push the string ";(%{}".format(source_code) (essentially "gcd(b, a % b)")
3δ       bring the second copy of b to TOS
I      if: pop b, recursive call, and "X", and push recursive call if b != 0 else "X"
£ƒ    call the string as a function
kΣ  sum stack elements (without this, the stack contains the gcd and possibly several 0's)


# T-SQL, 147 Bytes

SQL Fiddle

MS SQL Server 2014 Schema Setup:

CREATE PROC G @ INT,@B INT,@C INT OUT AS BEGIN IF @<@B EXEC G @B,@,@C OUT ELSE IF @B>0 BEGIN SELECT @=@%@B EXEC G @B,@,@C OUT END ELSE SET @C=@ END


Testing:

Use something like this to generate each set of results:

DECLARE @A INT,@B INT,@EXP INT,@RES INT
SELECT @A=0,@B=2,@EXP=2
EXEC G @A,@B,@RES OUT
SELECT @A A,@B B,@EXP EXPECTED,@RES RESULT

|  A  |  B  | EXPECTED | RESULT |
|-----|-----|----------|--------|
|   0 |   2 |        2 |      2 |
|   6 |   0 |        6 |      6 |
|  30 |  42 |        6 |      6 |
|  15 |  14 |        1 |      1 |
|   7 |   7 |        7 |      7 |
|  69 |  25 |        1 |      1 |
|  21 |  12 |        3 |      3 |
|  20 | 142 |        2 |      2 |
| 101 | 202 |      101 |    101 |


# Oracle SQL 11.2, 108 Bytes

CREATE PROCEDURE G(A INT,B INT,C OUT INT)AS BEGIN IF A>0 THEN G(LEAST(A,B),ABS(A-B),C);ELSE C:=B;END IF;END;


Testing:

CREATE FUNCTION testHelper(A INT,B INT) RETURN INT
AS
C INT;
BEGIN
G(A,B,C);
RETURN C;
END;
/

WITH tests( A, B, Expected ) AS (
SELECT   0,  2,  2 FROM DUAL UNION ALL
SELECT   6,  0,  6 FROM DUAL UNION ALL
SELECT  30, 42,  6 FROM DUAL UNION ALL
SELECT  15, 14,  1 FROM DUAL UNION ALL
SELECT   7,  7,  7 FROM DUAL UNION ALL
SELECT  69, 25,  1 FROM DUAL UNION ALL
SELECT  21, 12,  3 FROM DUAL UNION ALL
SELECT 169,123,  1 FROM DUAL UNION ALL
SELECT  20,142,  2 FROM DUAL UNION ALL
SELECT 101,202,101 FROM DUAL
)
SELECT t.*,testHelper(A,B) AS "RESULT"
FROM   tests t;


Output:

         A          B   EXPECTED     RESULT
---------- ---------- ---------- ----------
0          2          2          2
6          0          6          6
30         42          6          6
15         14          1          1
7          7          7          7
69         25          1          1
21         12          3          3
169        123          1          1
20        142          2          2
101        202        101        101


# J, 15 14 bytes

[(|$:[)@.(]*)  Uses Euclid's algorithm. ## Usage  f =: [(|$:[)@.(]*)
30 f 42
6
42 f 30
6
169 f 123
1


## Explanation

[(|$:[)@.(]*) Input: a, b ]* Get sign(b) If sign(n) = 0 [ Return a Else | Get b mod a [ Get a$:            Call recursively on (b mod a, a)


# Java 7, 42 bytes

int c(int a,int b){return b>0?c(b,a%b):a;}


Ungolfed & test cases:

Try it here.

class M{
static int c(int a, int b){
return b > 0
? c(b, a%b)
: a;
}

public static void main(String[] a){
System.out.println(c(0, 2));
System.out.println(c(6, 0));
System.out.println(c(30, 42));
System.out.println(c(15, 14));
System.out.println(c(7, 7));
System.out.println(c(69, 25));
System.out.println(c(21, 12));
System.out.println(c(169, 123));
System.out.println(c(20, 142));
System.out.println(c(101, 202));
}
}


Output:

2
6
6
1
7
1
3
1
2
101


# Javascript, 42 bytes

n=(x,y)=>{for(k=x;x%k+y%k>0;k--);alert(k)}


I could get it down to ~32 with Grond, but whatever

• You can save a byte with currying. Apr 9 '16 at 8:01
• Unfortunately, this doesn't work with the new test cases (in particular, 0, 2). Apr 9 '16 at 18:05
• What is currying? Apr 10 '16 at 19:24
• Dennis, 0 / 2 != 2. I say the test cases are wrong... sneaky face Apr 10 '16 at 19:25

# Mathematica, 27 bytes

If[#<1,#2,#0[#2,#~Mod~#2]]&


Not much to see here.

• Hey, I was going to post that! (No I wasn't, I didn't know that GCD existed.) Apr 7 '16 at 22:51
• -1 LCMGCD. Apr 8 '16 at 2:30
• Built-ins for GCD and LCM are disallowed. Oct 4 '16 at 14:40
• @LegionMammal978 And? Now it's invalid. Aka, delete it or fix it. Oct 4 '16 at 22:49

# MACHINE LANGUAGE(X86, 32 bit), 19 bytes

0000079C  8B442404          mov eax,[esp+0x4]
000007A0  8B4C2408          mov ecx,[esp+0x8]
000007A4  E308              jecxz 0x7ae
000007A6  31D2              xor edx,edx
000007A8  F7F1              div ecx
000007AA  92                xchg eax,edx
000007AB  91                xchg eax,ecx
000007AC  EBF6              jmp short 0x7a4
000007AE  C3                ret
000007AF


7AFh-79Ch=13h=19d (see other x86 solution too).Below assembly with the function, but for me gcd(a,b) if a or b is 0 has to return -1 error...

; nasmw -fobj  this.asm
; bcc32 -v  file.c this.obj
section _DATA use32 public class=DATA
global _gcda
section _TEXT use32 public class=CODE

_gcda:
mov     eax,  dword[esp+  4]
mov     ecx,  dword[esp+  8]
.1:   JECXZ   .z
xor     edx,  edx
div     ecx
xchg    eax,  edx
xchg    eax,  ecx
jmp     short  .1
.z:
ret


this is the C function for test, that call the gcda() function:

#include <stdio.h>
unsigned v0[]={30,15,7,69,21,169, 20,101,0,6,1,0};
unsigned v1[]={42,14,7,25,12,123,142,202,2,0,2,0};
unsigned gcda(unsigned,unsigned);

main(void)
{int  i;
for(i=0;v0[i]||v1[i];++i)
printf("gcd(%u,%u)=%u\n",v0[i],v1[i],gcda(v0[i],v1[i]));
return 0;
}


results:

gcd(30,42)=6
gcd(15,14)=1
gcd(7,7)=7
gcd(69,25)=1
gcd(21,12)=3
gcd(169,123)=1
gcd(20,142)=2
gcd(101,202)=101
gcd(0,2)=2
gcd(6,0)=6
gcd(1,2)=1


# APL(NARS), 13 chars, 26 bytes

{⍵<1:⍺⋄⍵∇⍵∣⍺}


test:

  g←{⍵<1:⍺⋄⍵∇⍵∣⍺}
30 g 42
6
42 g 30
6
15 g 14
1
7 g 7
7
69 g 25
1
0 g 2
2
6 g 0
6


# Smalltalk, 29 bytes

[(a:=b\\(b:=a))>0]whileTrue.b


## Explanation

a, b                  two integers given as input
b\\(b:=a)             compute (b mod a) and then assign a to b
a:=b\\(b:=a)          assign the remainder just computed to a
[(...)>0]whileTrue    repeat while the reminder a is > 0 (stop otherwise)
b                     return b (the gcd) - dot is a sentence separator

• Feel free to expand your answer by including an explanation and a link to an online interpreter. Not everyone here knows Smalltalk. When your answers are short and just code, they show in the "Low Quality Posts" queue and users have to review them. Take a look at answers by other users to see some examples. Mar 19 '19 at 15:11
• @mbomb007 Done. Thanks for the suggestion. Mar 19 '19 at 15:39

# Befunge-93, 22 bytes

&&:#v_\.@
p00:<^:\g00%


Try it online!

Doesn't beat Jo King's answer, but I already spent the time creating this answer before seeing their solution. C'est la vie. Uses the same Euclidean Algorithm as most answers.

# Japt-h, 5 bytes

Input as an array.

mâ rf


Try it

mâ rf     :Implicit input of integer array
m         :Map
â        :  Divisors
r      :Reduce by
f     :  Filtering, keeping only those elements in the first array that also appear in the second
:Implicit output of last element
`