# 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
• @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
• gcd(0,n) is error not n – RosLuP Mar 18 at 12:33

# Retina, 16

^(.+)\1* \1+1


This doesn't use Euclid's algorithm at all - instead it finds the GCD using regex matching groups.

Try it online. - This example calculates GCD(8,12).

Input as 2 space-separated integers. Note that the I/O is in unary. If that is not acceptable, then we can do this:

# Retina, 30

\d+
$* ^(.+)\1* \1+$
$1 1+$.&


Try it online.

As @MartinBüttner points out, this falls apart for large numbers (as is generally the case for anything unary). At very a minimum, an input of INT_MAX will require allocation of a 2GB string.

• I would like to vote for this more – MickyT Apr 8 '16 at 1:51
• Should be fine with the number range now. I've changed the spec (with the OPs permission) to require only the language's natural number range (or [0,255] if that's more). You'll have to support zeroes though, although I think changing your +s to *s should do. And you can significantly shorten the last stage of the long code by reducing it to 1. – Martin Ender Apr 10 '16 at 9:14
• For future reference, I just found an alternative 16-byte solution that works for an arbitrary number of inputs (including one) so it might be more useful in other contexts: retina.tryitonline.net/… – Martin Ender Sep 23 '16 at 11:15
• Just noticed that neither your solutions nor the one in my comment above needs the ^, because it's impossible for the match to fail from the starting position. – Martin Ender Dec 18 '17 at 11:01

# Forth (gforth), 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


# Forth (gforth), 52 bytes

: f begin 2dup max -rot min tuck mod ?dup 0= until ;


Try it online!

Uses Euclidean Algorithm [repeatedly call larger % smaller until result is 0]

### Code Explanation

: f               \ start a new word definition
begin           \ start and indefinite loop
2dup          \ duplicate arguments
max -rot min  \ reorder arguments so the smaller is on top
tuck          \ make a copy of the smaller argument and move it behind the larger
mod ?dup 0=   \ get the modulo of the two arguments, then duplicate and check if it is 0
until           \ end the loop if it is
;                 \ end the word definition


D,g,@@#~,%A$p%+ L,MRBCþgbM  Try it online! Generates the range $$\1, 2, 3, ..., \max(a, b)\$$, then filters out elements that don't divide either $$\a\$$ or $$\b\$$, Finally, we return the maximum value of the filtered elements. # 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. # 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.  ## Perl 6, 28 bytes my&f={$^b??f($b,$^a%$b)!!$a}


# 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. # 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 # 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  # 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  # Ink, 29 bytes =i(a,b) {b:->i(b,a%b)}{a}->->  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 # MATL, 11 9 bytes No one seems to have used brute force up to now, so here it is. ts:\a~f0)  Input is a column array with the two numbers (using ; as separator). ### Explanation t % Take input [a;b] implicitly. Duplicate s % Sum. Gives a+b : % Array [1,2,...,a+b] \ % Modulo operation with broadcast. Gives a 2×(a+b) array a~ % 1×(a+b) array that contains true if the two modulo operations gave 0 f0) % Index of last true value. Implicitly display  # Japt, 18 bytes wV Ä o a@!UuX «VuX  Brute force, tries every integer. Try it online! # C, 38 bytes g(x,y){while(x^=y^=x^=y%=x);return y;}  • You need to include the definition of the function in your bytecount. – Rɪᴋᴇʀ Dec 29 '17 at 0:24 • @Riker sorry for that, I add the definition and update the count – How Chen Dec 29 '17 at 0:32 • You can save two bytes by naming the function just g instead of gcd. – Steadybox Dec 29 '17 at 0:37 • @Steadybox ok, yes, first time join this community:) – How Chen Dec 29 '17 at 0:38 • Welcome to PPCG! – Rɪᴋᴇʀ Dec 29 '17 at 0:38 # 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 # Befunge-93, 21 bytes &&:v_.@ 00:_^#:%g00\p  Try it Online Yet another Euclidean algorithm # 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 # 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 # ReRegex, 23 bytes Works identically to the Retina answer. ^(_*)\1* \1*$/$1/#input  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 # Perl 5, 51 bytes 49bytes of code + 2 flags (-pa) $b=pop@F;($_,$b)=(abs$_-$b,$_>$b?$b:$_)while$_-$b


Try it online!

# Python 3, 31

Saved 3 bytes thanks to Sp3000.

g=lambda a,b:b and g(b,a%b)or a

• In Python 3.5+: from math import*;gcd – Sp3000 Apr 7 '16 at 18:11
• @Sp3000 Nice, I didn't know they had moved it to math. – Morgan Thrapp Apr 7 '16 at 18:12
• While you're at it: g=lambda a,b:b and g(b,a%b)or a – Sp3000 Apr 7 '16 at 18:15
• @Sp3000 Thanks! I just finished a recursive solution, but that's even better than what I had. – Morgan Thrapp Apr 7 '16 at 18:16
• Built-ins for GCD and LCM are disallowed, so the 2nd solution wouldn't be valid. – mbomb007 Oct 4 '16 at 14:38

# 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