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 '16 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 '16 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 '16 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 '16 at 14:10
  • 2
    \$\begingroup\$ gcd(0,n) is error not n \$\endgroup\$
    – user58988
    Mar 18 '19 at 12:33

74 Answers 74

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

Rust, 39 bytes

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

Try it online!

\$\endgroup\$
1
\$\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 '21 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 '21 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 '21 at 16:52
  • \$\begingroup\$ @hyper-neutrino are you console logging it \$\endgroup\$ Dec 18 '21 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 '21 at 9:31
1
\$\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\$
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 '16 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 '16 at 19:39
  • 7
    \$\begingroup\$ I think the question disallows using a GCD builtin. \$\endgroup\$
    – Cyoce
    Apr 9 '16 at 23:10
0
\$\begingroup\$

Befunge-93, 21 bytes

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

Try it Online

Yet another Euclidean algorithm

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

Ink, 29 bytes

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

Try it online!

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

Perl 6, 28 bytes

my&f={$^b??f($b,$^a%$b)!!$a}
\$\endgroup\$
0
0
\$\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\$
0
\$\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 2
3

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.