43
\$\begingroup\$

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
\$\endgroup\$
6
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Apr 8, 2016 at 23:05
  • \$\begingroup\$ @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. \$\endgroup\$ Apr 9, 2016 at 18:59
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 9, 2016 at 19:30
  • 3
    \$\begingroup\$ @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? \$\endgroup\$ Apr 10, 2016 at 14:10
  • 2
    \$\begingroup\$ gcd(0,n) is error not n \$\endgroup\$
    – user58988
    Mar 18, 2019 at 12:33

74 Answers 74

2
\$\begingroup\$

Ruby, 23 bytes

g=->a,b{b>0?a:g[b,a%b]}

remember that ruby blocks are called with g[...] or g.call(...), instead of g(...)

partial credits to voidpigeon

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Instead of g.call(a,b) you can use g[a,b]. Instead of proc{|a,b|, you can use ->a,b{. \$\endgroup\$
    – afuous
    Apr 7, 2016 at 23:33
  • 1
    \$\begingroup\$ You can also save one byte by using b>0 instead of b<=0 and switching the order of the other operands. \$\endgroup\$
    – afuous
    Apr 7, 2016 at 23:35
2
\$\begingroup\$

ARM machine code, 12 bytes:

assembly:

gcd: cmp r0, r1
     sublt r0, r0, r1
     bne gcd

Currently can't compile this, but each instruction in ARM takes 4 bytes. Probably it could be golfed down using THUMB-2 mode.

\$\endgroup\$
5
  • \$\begingroup\$ Nice job man anyone who does this in machine code gets serious props from me. \$\endgroup\$ Apr 8, 2016 at 20:15
  • \$\begingroup\$ This appears to be an attempt at Euclid's algo using only subtraction, but I don't think it works. If r0 > r1 then sublt will do nothing (lt predicate is false) and bne will be an infinite loop. I think you need a swap if not lt, so the same loop can do b-=a or a-=b as needed. Or a negate if the sub produced carry (aka borrow). \$\endgroup\$ Apr 9, 2016 at 18:55
  • \$\begingroup\$ This ARM instruction set guide actually uses a subtraction GCD algorithm as an example for predication. (pg 25). They use cmp r0, r1 / subgt r0, r0, r1 / sublt r1, r1, r0 / bne gcd. That's 16B in ARM instructions, maybe 12 in thumb2 instructions? \$\endgroup\$ Apr 9, 2016 at 19:21
  • 1
    \$\begingroup\$ On x86, I managed 9 bytes with: sub ecx, eax / jae .no_swap / add ecx,eax / xchg ecx,eax / jne. So instead of a cmp, I just sub, then undo and swap if the sub should have gone the other way. I tested this, and it works. (add won't make jne exit at the wrong time, because it can't produce a zero unless one of the inputs was zero to start with, and we don't support that. Update: we do need to support either input being zero :/) \$\endgroup\$ Apr 9, 2016 at 19:25
  • \$\begingroup\$ For Thumb2, there's an ite instruction: if-then-else. Should be perfect for cmp / sub one way / sub the other way. \$\endgroup\$ Apr 9, 2016 at 23:23
2
\$\begingroup\$

TI-Basic, 10 bytes

Prompt A,B:gcd(A,B

Non-competing due to new rule forbidding gcd built-ins


17 byte solution without gcd( built-in

Prompt A,B:abs(AB)/lcm(A,B

Non-competing due to new rule forbidding lcm built-ins


27 byte solution without gcd( or lcm( built-in:

Prompt A,B:While B:B→T:BfPart(A/B→B:T→A:End:A

35 byte recursive solution without gcd( or lcm( built-ins (requires 2.53 MP operating system or higher, must be named prgmG):

If Ans(2:Then:{Ans(2),remainder(Ans(1),Ans(2:prgmG:Else:Disp Ans(1:End

You would pass arguments to the recursive variant as {A,B} so for example {1071, 462}:prgmG would yield 21.

\$\endgroup\$
2
  • \$\begingroup\$ Color me impressed. \$\endgroup\$ Apr 7, 2016 at 18:57
  • \$\begingroup\$ You should probably mention that the last one needs to be saved as prgmG. \$\endgroup\$ Apr 7, 2016 at 19:48
2
\$\begingroup\$

05AB1E, 10 bytes

Code:

EàF¹N%O>iN

Try it online!


With built-ins:

¿

Explanation:

¿   # Implicit input, computes the greatest common divisor.
    # Input can be in the form a \n b, which computes gcd(a, b)
    # Input can also be a list in the form [a, b, c, ...], which computes the gcd of
      multiple numbers.

Try it online! or Try with multiple numbers.

\$\endgroup\$
0
2
\$\begingroup\$

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

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

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Built-ins are disallowed in the challenge specification. \$\endgroup\$
    – rturnbull
    Oct 4, 2016 at 14:02
  • \$\begingroup\$ I have corrected the answer. \$\endgroup\$
    – rnso
    Oct 4, 2016 at 16:32
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Java, 38 bytes

f=(int a,b)->{return b==0?a:f(b,a%b);}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$
    – Riker
    Dec 18, 2017 at 0:58
  • \$\begingroup\$ @Ricker thanks :) (I'm assuming that stands for programming puzzles code golf) \$\endgroup\$
    – Justin
    Dec 18, 2017 at 1:45
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

Japt, 18 bytes

wV Ä o a@!UuX «VuX

Brute force, tries every integer.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – mbomb007
    Mar 19, 2019 at 15:11
  • \$\begingroup\$ @mbomb007 Done. Thanks for the suggestion. \$\endgroup\$ Mar 19, 2019 at 15:39
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

APL (NARS2000), 11 chars, 20 bytes

{×/(π⍺)∩π⍵}

Examples:

      28{×/(π⍺)∩π⍵}144
4
      69{×/(π⍺)∩π⍵}25
1

Why it works:

Function π, when applied monadically, breaks down argument into prime factors. (π⍺)∩π⍵ gives intersection of prime factors of left and right argument. ×/ multiplies prime factors in the intersection, giving the largest divisor common to and w. In case and w are co-prime then reducing empty intersection would give 1.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 58 bytes

lambda a,b:max(n for n in range(1,max(a,b)+1)if a%n+b%n<1)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

BQN, 11 bytesSBCS

{𝕨(|𝕊⊣)⍟𝕨𝕩}

Run online!

3 bytes shorter and a lot less efficient than the version provided on BQNcrate: {𝕨(|𝕊⍟(>⟜0)⊣)𝕩}

This is a dyadic function with arguments 𝕨 and 𝕩.

With left argument 𝕨 and starting with 𝕩 as a right argument, call (|𝕊⊣) 𝕨 times, updating the right argument with the return value. 𝕊 refers to the full function and |𝕊⊣ does a recursive call with 𝕨|𝕩 (𝕩 mod 𝕨) as left and 𝕨 as right argument.

It would be enough to call the inner function just once if 𝕨 is positive, and not at all if 𝕨 is 0, but ⍟(×𝕨) is just too long.

\$\endgroup\$
2
\$\begingroup\$

Rust, 39 bytes

|a,b|(1..=a+b).rev().find(|i|a%i+b%i<1)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Javascript, 48 bytes

$=((r,a)=>{for(;a;){var e=a;a=r%a,r=e}return r})
\$\endgroup\$
6
  • \$\begingroup\$ I'm not quite sure how to test this - when I run it like this it doesn't terminate - how should I run this? \$\endgroup\$
    – hyper-neutrino
    Dec 18, 2021 at 16:17
  • \$\begingroup\$ @hyper-neutrino its a function so you need to run it with the parameters being two numbers that you want to find the GCD of. E.g a(2,5) \$\endgroup\$ Dec 18, 2021 at 16:50
  • \$\begingroup\$ In my linked example I tried running a(30, 42) and it didn't work. Perhaps the variable name duplication is causing some issues here? \$\endgroup\$
    – hyper-neutrino
    Dec 18, 2021 at 16:52
  • \$\begingroup\$ @hyper-neutrino are you console logging it \$\endgroup\$ Dec 18, 2021 at 17:02
  • 1
    \$\begingroup\$ @hyper-neutrino I have rewritten it and now it should be supported by any version above ES6. It works completely fine for me and I've tried two different computers \$\endgroup\$ Dec 19, 2021 at 9:31
2
\$\begingroup\$

Nibbles, 5 bytes (10 nibbles)

`;~$@@$_@%

Verbose

`;   # Recursive function
  ~ $ @   # Call it with the first two command-line arguments (m,n)
  @   # Recurse if n is truthy
  $   # Base case = m
  _ @ %   # Recursive case = gcd(n, m mod n)
\$\endgroup\$
1
\$\begingroup\$

Scheme, 44 bytes

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

Scheme is the future of code-golf. :)

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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

Results:

|  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 |
\$\endgroup\$
1
\$\begingroup\$

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 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.