47
\$\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\$
7
  • 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
  • 4
    \$\begingroup\$ gcd(0,n) is error not n \$\endgroup\$
    – user58988
    Mar 18, 2019 at 12:33

85 Answers 85

1 2
3
2
\$\begingroup\$

Piet + ascii-piet, 42 bytes (2×21=42 codels)

qbdijbrlkumldqralckkB   jj   s??venvfff bb

Try Piet online!

\$\endgroup\$
2
  • \$\begingroup\$ Very obvious 48 bytes that I noticed at first glance. \$\endgroup\$
    – Aiden Chow
    Mar 8, 2023 at 5:32
  • \$\begingroup\$ 42 bytes \$\endgroup\$
    – Aiden Chow
    Mar 8, 2023 at 5:47
2
\$\begingroup\$

Vyxal, 13 bytes

∴ƛ□$%∑¬;¦:Gḟ›

Try it Online!

Thanks to @Fhuvi for pointing out a bug.

Explanation:

∴ƛ□$%∑¬;¦:Gḟ›  # Implicit inputs
∴              # Maximum input
 ƛ     ;       # Map over range(1, ^ + 1):
  □$           #  Push input list and swap
    %∑         #  Sum of each input mod the number
      ¬        #  Equals 0?
        ¦      # Cumulative sums of the list
         :G    # Maximum of that list
           ḟ   # Index of that in the cumulative sums
            ›  # Plus one to account for 0-indexing
               # Implicit output
\$\endgroup\$
4
  • \$\begingroup\$ "You are not allowed to use built-ins that compute either the GCD or the LCM (least common multiple)." \$\endgroup\$
    – naffetS
    Jan 8, 2023 at 14:43
  • \$\begingroup\$ Yeah, I just saw that. Sorry. \$\endgroup\$
    – The Thonnu
    Jan 8, 2023 at 14:43
  • \$\begingroup\$ Sorry if this adds more work (or bytes), but it seems to not work properly if the first parameter is zero ^^' \$\endgroup\$
    – Fhuvi
    Mar 9, 2023 at 17:25
  • 1
    \$\begingroup\$ @Fhuvi thanks for noticing. That's easily fixed, by adding a at the start. \$\endgroup\$
    – The Thonnu
    Mar 9, 2023 at 18:41
2
\$\begingroup\$

Thunno, \$ 19 \log_{256}(96) \approx \$ 15.64 bytes

~e1+I$S0=Ez(DMsAh1+

Attempt This Online!

Thanks to @Fhuvi for pointing out a bug.

Explanation

~e1+I$S0=Ez(DMsAh1+  # Implicit input
~                    # First non-zero input
 e       E           # Map over the range:
  1+                 #  Increment
    I$               #  Mod the input list
      S0=            #  Sum equals 0
          z(         # Cumulative sums
            DM       # Maximum
              sAh    # Index of this in the list
                 1+  # Incremented
                     # Implicit output

Old one which didn't work for 0:

eI$S0=Ez(DMsAh  # Implicit input
e     E         # Map over range:
 I$             #  This number mod the input list
   S0=          #  Sum equals 0
       z(       # Cumulative sums
         DM     # Maximum
           sAh  # Index of this in the list
                # Implicit output
\$\endgroup\$
2
  • \$\begingroup\$ Sorry again, but it seems to not work properly if one of the parameters is zero ^^' \$\endgroup\$
    – Fhuvi
    Mar 9, 2023 at 17:28
  • 1
    \$\begingroup\$ @Fhuvi fixed at the cost of 5 characters \$\endgroup\$
    – The Thonnu
    Mar 9, 2023 at 18:43
2
\$\begingroup\$

C, 23 bytes

f(x,y){x=x?f(y%x,x):y;}

Essentially Euclid's algorithm in a ternary expression with recursion.

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

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

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

Mathematica, 27 bytes

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

Not much to see here.

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

Befunge-93, 21 bytes

&&:v_.@
00:_^#:%g00\p

Try it Online

Yet another Euclidean algorithm

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

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

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

Ink, 29 bytes

=i(a,b)
{b:->i(b,a%b)}{a}->->

Try it online!

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

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
\$\endgroup\$
1
  • \$\begingroup\$ The loop is the same as the unsigned 32-bit version described in my answer, except without the inc/loop` optimization (3 bytes in 32-bit mode vs. 2+2=4 for JECXZ/JMP), so it's safer with a 0 input. Plus loading args from the stack, instead of using a better calling convention like GCC's __attribute__((regparm(3))) (EAX, EDX, ECX in that order). Even for stack args, you could do 3x pop, then 3x push to put things back (including the return address), leaving values in regs in 6 bytes instead of 8 for 2x 4 (mov_opcode + modrm + sib + disp8) \$\endgroup\$ Sep 28, 2022 at 10:41
1
\$\begingroup\$

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

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.

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

Perl 6, 28 bytes

my&f={$^b??f($b,$^a%$b)!!$a}
\$\endgroup\$
0
1
\$\begingroup\$

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

Ral, 45 37 bytes

,:,+0=0*/-:1+1:+1+:+:1=?0*+0*/:0=1*?.

Try it online! (inputs on separate lines)

Commented:

,:,                  Input a and b
+0=                  Add a to b
                   Loop:
0*/-                 Subtract b from a
:1+1:+1+:+:1=?       Continue if a >= 0
0*+                  Add b to a
0*/:0=               Swap a and b
1*?                  Continue if b > 0
.                    Print a
\$\endgroup\$
1
\$\begingroup\$

Zsh, 29 bytes

(($1))&&$0 $[$2%$1] $1||<<<$2

Try it online!

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

Thunno 2, 10 bytes

GıḊp;ṡDGȮ⁺

Attempt This Online!

Port of my Vyxal answer.

Explanation

GıḊp;ṡDGȮ⁺  # Implicit input
Gı  ;       # Map over (the one-range of) the higher number:
  Ḋ         #  Is each input divisible by this number?
   p        #  Are both true?
     ṡ      # Cumulative sums of this list
      DG    # Without popping, push the maximum
        Ȯ⁺  # 1-based index of the maximum
            # Implicit output
\$\endgroup\$
1
\$\begingroup\$

Vyxal G, 37 bitsv1, 4.625 bytes

vKƒ↔∨

Try it Online!

Why use ranges and sums when a more logical approach is shorter :p

Takes input as a list of numbers.

Explained

vKƒ↔∨
vK      # Get the divisors of each number
  ƒ↔    # reduce by set intersection. This will either give a list of shared divisors or an empty list. You only get an empty list if there is a 0 in the input. 
     ∨  # logical or with the input, getting the first truthy value. If there's a 0 in the input, this returns the input list
# The G flag gets the biggest of either the shared factors or the input list if there's a 0.
\$\endgroup\$
1
\$\begingroup\$

Nekomata, 5 bytes

ṀRᶠ¦Ṁ

Attempt This Online!

Takes a list of two numbers as input.

ṀRᶠ¦Ṁ
Ṁ       Maximum of the input
 R      Range from 1 to that
  ᶠ     Filter by the following function:
   ¦      Check that it divides both numbers in the input
    Ṁ   Maximum of the resulting list

Nekomata, 6 bytes

ʷ{$ᵉ%Z

Attempt This Online!

Using the Euclidean algorithm.

ʷ{$ᵉ%Z
ʷ{      Apply the following function repeatedly until it fails:
          Let the stack be a, b
  $       a, b -> b, a
   ᵉ%     b, a -> b, a % b
     Z    Check that b is not zero
\$\endgroup\$
0
\$\begingroup\$

Pyth, 2 bytes

iE

Try it here!

Input as integer on two separate lines. Just uses a builtin.

\$\endgroup\$
3
  • \$\begingroup\$ Haha, I like it. \$\endgroup\$ Apr 7, 2016 at 18:06
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Apr 7, 2016 at 19:39
  • 10
    \$\begingroup\$ I think the question disallows using a GCD builtin. \$\endgroup\$
    – Cyoce
    Apr 9, 2016 at 23:10
1 2
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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