# 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. – Peter Cordes 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. – Mike Shlanta 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. – Peter Cordes Apr 9 '16 at 19:30
• @Martin Doesn't your edit make it impossible to implement this in languages where the default integer type is immutable and only limited by the available memory? – CodesInChaos Apr 10 '16 at 12:24
• @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? – Martin Ender Apr 10 '16 at 14:10

# 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.

# PHP, 41 51 bytes

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. – rturnbull 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

# R, 39 33 bytes

Surprised not to see an R answer on here yet. A recursive implementation of the Euclidean algorithm. Saved 2 bytes due to Giuseppe.

g=pryr::f(if(o<-x%%y,g(y,o),y))


And here is a vectorized version (35 bytes) which works well for problems like Natural pi calculation.

g=pryr::f(ifelse(o<-x%%y,g(y,o),y))

• "if" rather than ifelse for -2 bytes, but you lose the vectorization... – Giuseppe Sep 5 '17 at 2:29
• @Giuseppe Thanks, good catch! – rturnbull Sep 6 '17 at 22:15

# 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

# 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.

   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. – Cyoce Apr 9 '16 at 8:01 • Unfortunately, this doesn't work with the new test cases (in particular, 0, 2). – Dennis Apr 9 '16 at 18:05 • What is currying? – Bald Bantha Apr 10 '16 at 19:24 • Dennis, 0 / 2 != 2. I say the test cases are wrong... sneaky face – Bald Bantha Apr 10 '16 at 19:25 # 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 # 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! – Rɪᴋᴇʀ Dec 18 '17 at 0:58 • @Ricker thanks :) (I'm assuming that stands for programming puzzles code golf) – Justin Dec 18 '17 at 1:45 # Proton, 21 bytes f=(a,b)=>b?f(b,a%b):a  Try it online! Shush you, this is totally not a port of the Python answer. • Conditional operator is shorter: f=(x,y)=>y? f(y,x%y):x (yes the space is necessary due to an interpreter bug) – Business Cat Aug 18 '17 at 20:14 • ...Right, I need to start thinking Proton, not Python. Thanks! – totallyhuman Aug 18 '17 at 20:16 # 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. – Dennis Apr 7 '16 at 18:21 • @Dennis I think I just fixed it? Like I said, super new to JS. – Morgan Thrapp Apr 7 '16 at 18:22 • Yes, that works. For the record, g=(a,b)=>b?a:g(b,a%b) is equally short. – Dennis 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. – Morgan Thrapp 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 – user81655 Apr 8 '16 at 3:39 # Pyth, 2 bytes iE  Try it here! Input as integer on two separate lines. Just uses a builtin. • Haha, I like it. – Mike Shlanta Apr 7 '16 at 18:06 • If you change the input format, iF also works. In addition, I think M?HgH%GHG is the shortest no-builtin way of doing this. – FryAmTheEggman Apr 7 '16 at 19:39 • I think the question disallows using a GCD builtin. – Cyoce Apr 9 '16 at 23:10 # 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.) – CalculatorFeline Apr 7 '16 at 22:51 • -1 LCMGCD. – CalculatorFeline Apr 8 '16 at 2:30 • Built-ins for GCD and LCM are disallowed. – mbomb007 Oct 4 '16 at 14:40 • @LegionMammal978 And? Now it's invalid. Aka, delete it or fix it. – mbomb007 Oct 4 '16 at 22:49 # Befunge-93, 21 bytes &&:v_.@ 00:_^#:%g00\p  Try it Online Yet another Euclidean algorithm # Japt, 18 bytes wV Ä o a@!UuX «VuX  Brute force, tries every integer. Try it online! # Japt, 9 bytes V?ßVU%V:U  Run it online 8 bytes if we can reverse the order of the input: ?ßV%UU:V  Run it online # Ink, 29 bytes =i(a,b) {b:->i(b,a%b)}{a}->->  Try it online! # 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. – mbomb007 Mar 19 at 15:11 • @mbomb007 Done. Thanks for the suggestion. – Leandro Caniglia Mar 19 at 15:39 # AWK, 39 bytes {for(x=$1>$2?$1:$2;$1%x||$2%x;)--x}$0=x


Try it online!

Does require that 1 of the inputs be positive. Nothing fancy, but I don't see another AWK solution.

## Perl 6, 28 bytes

my&f={$^b??f($b,$^a%$b)!!\$a}
`