Greatest Common Divisor

Question

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 code-golf 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

Answer 1

bash, 37

Recursive:

g(){ (($2))&&g $2 $[$1%$2]||echo $1;}

But for making useful function, I prefer assigning variable in order to avoid forks. So I will prefer this for loop:

for((i=$1,l=$2;l;k=l,l=i%l,i=k)){ :;}

Note: both routines use 37 characters!

Test cases

for pair in 0\ 2 6\ 0 30\ 42 15\ 14 7\ 7 69\ 25 21\ 12 169\ 123 20\ 142 101\ 202;do
    printf '%4d %4d => %3d\n' $pair $(g $pair)
done
   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

As a dedicated function:

gcd() {
    if [[ $1 == -v ]];then local -n i=$2;shift 2;else local i;fi
    local l=$2 k
    for((i=$1;l;k=l,l=i%l,i=k)){ :;}
    [[ ${i@A} != i=* ]] || echo "$i"
}

Test cases

for pair in 0:2 6:0 30:42 15:14 7:7 69:25 21:12 169:123 20:142 101:202;do
    IFS=: read -ra vals <<<$pair
    gcd -v res ${vals[@]}
    printf '    %4d %4d => %3d\n' ${vals[@]} $res
done
   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

Answer 2

GML, 57 bytes

a=argument0
b=argument1
while b{t=b;b=a mod b;a=t}return a

Answer 3

Delphi 7, 148

Well, I think I've found the new worst language for golfing.

unit a;interface function g(a,b:integer):integer;implementation function g(a,b:integer):integer;begin if b=0then g:=a else g:=g(b,a mod b);end;end.

Answer 4

Hoon, 20 bytes

|=
{@ @}
d:(egcd +<)

--

Hoon #2, 39 bytes

|=
{a/@ b/@}
?~
b
a
$(a b, b (mod a b))

Oddly, the only implementation in Hoon's stdlib for GCD is the one in use for its RSA crypto, which also returns some other values. I have to wrap it in a function that takes only d from the output.

The other implementation is just the default recursive GCD definition.

Answer 5

Python 3.5, 70 82 73 bytes:

lambda*a:max([i for i in range(1,max(*a)+1)if not sum(g%i for g in[*a])])

The not in this case will make sure the sum all the numbers in *args modulo i are zero.

Also, now this lambda function can take in as many values as you want it to, as long as the amount of values is >=2, unlike the gcd function of the math module. For instance, it can take in the values 2,4,6,8,10 and return the correct GCD of 2.

Answer 6

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

Answer 7

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.

Answer 8

Scheme, 44 bytes

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

Scheme is the future of code-golf. :)

Answer 9

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

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

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

Answer 14

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.

Answer 15

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

Answer 16

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!

Answer 17

Java, 38 bytes

f=(int a,b)->{return b==0?a:f(b,a%b);}

Answer 18

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

Answer 19

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

Answer 20

Japt, 18 bytes

wV Ä o a@!UuX «VuX

Brute force, tries every integer.

Try it online!

Answer 21

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

Answer 22

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.

Answer 23

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

Answer 24

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.

Answer 25

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!

Answer 26

BQN, 11 bytes^SBCS

{𝕨(|𝕊⊣)⍟𝕨𝕩}

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.

Answer 27

Javascript, 48 bytes

$=((r,a)=>{for(;a;){var e=a;a=r%a,r=e}return r})

Answer 28

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)

Answer 29

jq, 30 bytes

Takes a list of two numbers

until(min<1;[max-min,min])|max

Try it online!

Answer 30

Desmos, 44 bytes

f(l)=[i0^{mod(l,i).max}fori=[1...l.max]].max

Try it on Desmos!

Input is a list of two integers. It won't work if at least one of the inputs is greater than 10000 because of list length limits, so this is possibly non-competing.