Greatest common divisor: Difference between revisions

From Rosetta Code
Content added Content deleted
(+ Pascal)
(added ruby)
Line 3: Line 3:


=={{header|Ada}}==
=={{header|Ada}}==
with Ada.Text_Io; use Ada.Text_Io;
<ada>with Ada.Text_Io; use Ada.Text_Io;

procedure Gcd_Test is
procedure Gcd_Test is
function Gcd (A, B : Integer) return Integer is
function Gcd (A, B : Integer) return Integer is
begin
begin
if A = 0 then
if A = 0 then
return B;
return B;
end if;
end if;
if B = 0 then
if B = 0 then
return A;
return A;
end if;
end if;
if A > B then
if A > B then
return Gcd(B, A mod B);
return Gcd(B, A mod B);
else
else
return Gcd(A, B mod A);
return Gcd(A, B mod A);
end if;
end if;
end Gcd;
end Gcd;
begin
begin
Put_Line("GCD of 100, 5 is" & Integer'Image(Gcd(100, 5)));
Put_Line("GCD of 100, 5 is" & Integer'Image(Gcd(100, 5)));
Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100)));
Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100)));
Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23)));
Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23)));
end Gcd_Test;
end Gcd_Test;</ada>


Output:
Output:
Line 70: Line 70:
=={{header|C}}==
=={{header|C}}==
===Iterative Euclid algorithm===
===Iterative Euclid algorithm===
int
<c>int
gcd_iter(int u, int v) {
gcd_iter(int u, int v) {
int t;
int t;
while (v) {
while (v) {
t = u;
t = u;
u = v;
u = v;
v = t % v;
v = t % v;
}
}
return u < 0 ? -u : u; /* abs(u) */
return u < 0 ? -u : u; /* abs(u) */
⚫
}</c>
}


===Recursive Euclid algorithm===
===Recursive Euclid algorithm===
int
<c>int
gcd(int u, int v) {
gcd(int u, int v) {
if (v)
if (v)
return gcd(v, u % v);
return gcd(v, u % v);
else
else
return u < 0 ? -u : u; /* abs(u) */
return u < 0 ? -u : u; /* abs(u) */
}</c>
}


===Iterative binary algorithm===
===Iterative binary algorithm===
<pre>
<c>int
int
gcd_bin(int u, int v) {
gcd_bin(int u, int v) {
int t, k;
int t, k;
Line 125: Line 124:
}
}
return u * k;
return u * k;
}</c>
}
⚫
</pre>


===Notes on performance===
===Notes on performance===
Line 228: Line 226:
=={{header|Java}}==
=={{header|Java}}==
===Iterative===
===Iterative===
public static long gcd(long a, long b){
<java>public static long gcd(long a, long b){
long factor= 0;
long factor= Math.max(a, b);
for(long loop= factor;loop > 1;loop--){
factor= Math.max(a, b);
for(long loop= factor;loop > 1;loop--){
if(a % loop == 0 && b % loop == 0){
if(a % loop == 0 && b % loop == 0){
return loop;
return loop;
}
}
}
}
return 1;
}</java>
⚫
return 1;
}


===Recursive===
===Recursive===
public static long gcd(long a, long b){
<java>public static long gcd(long a, long b){
if(a == 0) return b;
if(a == 0) return b;
if(b == 0) return a;
if(b == 0) return a;
if(a > b) return gcd(b, a % b);
if(a > b) return gcd(b, a % b);
return gcd(a, b % a);
return gcd(a, b % a);
}</java>
}


=={{header|Joy}}==
=={{header|Joy}}==
Line 310: Line 307:


=={{header|OCaml}}==
=={{header|OCaml}}==
let rec gcd a b =
<ocaml>let rec gcd a b =
if a = 0 then b
if a = 0 then b
else if b = 0 then a
else if b = 0 then a
else if a > b then gcd b (a mod b)
else if a > b then gcd b (a mod b)
else gcd a (b mod a)
else gcd a (b mod a)</ocaml>


=={{header|Pascal}}==
=={{header|Pascal}}==
⚫
<pascal>function gcd(a, b: integer): integer;
<pascal>
⚫
function gcd(a, b: integer): integer;
var
var
tmp: integer;
tmp: integer;
Line 329: Line 325:
end;
end;
gcd := a
gcd := a
end;
end;</pascal>
</pascal>


=={{header|Perl}}==
=={{header|Perl}}==
===Iterative Euclid algorithm===
===Iterative Euclid algorithm===
sub gcd_iter($$) {
<perl>sub gcd_iter($$) {
($u, $v) = @_;
my ($u, $v) = @_;
while ($v) {
while ($v) {
$t = $u;
($u, $v) = ($v, $u % $v);
⚫
}
⚫
$u = $v;
⚫
return abs($u);
$v = $t % $v;
}</perl>
⚫
}
return abs($u);
}


===Recursive Euclid algorithm===
===Recursive Euclid algorithm===
sub gcd($$) {
<perl>sub gcd($$) {
($u, $v) = @_;
my ($u, $v) = @_;
if ($v) {
if ($v) {
return gcd($v, $u % $v);
return gcd($v, $u % $v);
} else {
} else {
return abs($u);
return abs($u);
}
}
}</perl>
}


===Iterative binary algorithm===
===Iterative binary algorithm===
sub gcd_bin($$) {
<perl>sub gcd_bin($$) {
($u, $v) = @_;
my ($u, $v) = @_;
$u = abs($u);
$u = abs($u);
$v = abs($v);
$v = abs($v);
if ($u < $v) {
if ($u < $v) {
$t = $u;
($u, $v) = ($v, $u);
⚫
}
$u = $v;
$v = $t;
if ($v == 0) {
}
return $u;
⚫
}
if ($v == 0) {
return $u;
my $k = 1;
⚫
while ($u & 1 == 0 && $v & 1 == 0) {
⚫
}
$k = 1;
$u >>= 1;
while ($u & 1 == 0 && $v & 1 == 0) {
$v >>= 1;
$u >>= 1;
$k <<= 1;
}
$v >>= 1;
$k <<= 1;
my $t = ($u & 1) ? -$v : $u;
}
while ($t) {
$t = ($u & 1) ? -$v : $u;
while ($t & 1 == 0) {
while ($t) {
$t >>= 1;
}
⚫
while ($t & 1 == 0) {
$t >>= 1;
if ($t > 0) {
}
$u = $t;
if ($t > 0) {
} else {
$u = $t;
$v = -$t;
} else {
}
$v = -$t;
$t = $u - $v;
}
}
$t = $u - $v;
return $u * $k;
}</perl>
⚫
}
return $u * $k;
}


===Notes on performance===
===Notes on performance===
use Benchmark qw(cmpthese);
<perl>use Benchmark qw(cmpthese);

$u = 40902;
my $u = 40902;
$v = 24140;
my $v = 24140;
(-5, {
cmpthese(-5, {
'gcd' => sub { gcd($u, $v); },
'gcd' => sub { gcd($u, $v); },
'gcd_iter' => sub { gcd_iter($u, $v); },
'gcd_iter' => sub { gcd_iter($u, $v); },
'gcd_bin' => sub { gcd_bin($u, $v); },
'gcd_bin' => sub { gcd_bin($u, $v); },
});
});</perl>


Output on 'Intel(R) Pentium(R) 4 CPU 1.50GHz' / Linux / Perl 5.8.8:
Output on 'Intel(R) Pentium(R) 4 CPU 1.50GHz' / Linux / Perl 5.8.8:
Line 444: Line 435:
=={{header|Python}}==
=={{header|Python}}==
===Iterative Euclid algorithm===
===Iterative Euclid algorithm===
def gcd_iter(u, v):
<python>def gcd_iter(u, v):
while v:
while v:
u, v = v, u % v
u, v = v, u % v
return abs(u)
return abs(u)</python>


===Recursive Euclid algorithm===
===Recursive Euclid algorithm===
'''Interpreter:''' [[Python]] 2.5
'''Interpreter:''' [[Python]] 2.5
def gcd(u, v):
<python>def gcd(u, v):
return gcd(v, u % v) if v else abs(u)
return gcd(v, u % v) if v else abs(u)</python>


===Tests===
===Tests===
Line 468: Line 459:
===Iterative binary algorithm===
===Iterative binary algorithm===
See [[The Art of Computer Programming]] by Knuth (Vol.2)
See [[The Art of Computer Programming]] by Knuth (Vol.2)
def gcd_bin(u, v):
<python>def gcd_bin(u, v):
u, v = abs(u), abs(v) # u >= 0, v >= 0
u, v = abs(u), abs(v) # u >= 0, v >= 0
if u < v:
if u < v:
u, v = v, u # u >= v >= 0
u, v = v, u # u >= v >= 0
if v == 0:
if v == 0:
return u
return u
# u >= v > 0
# u >= v > 0
k = 1
k = 1
while u & 1 == 0 and v & 1 == 0: # u, v - even
while u & 1 == 0 and v & 1 == 0: # u, v - even
u >>= 1; v >>= 1
u >>= 1; v >>= 1
k <<= 1
k <<= 1
t = -v if u & 1 else u
t = -v if u & 1 else u
while t:
while t:
while t & 1 == 0:
while t & 1 == 0:
t >>= 1
t >>= 1
if t > 0:
if t > 0:
u = t
u = t
else:
else:
v = -t
v = -t
t = u - v
t = u - v
return u * k
return u * k</python>


===Notes on performance===
===Notes on performance===
Line 498: Line 489:


<code>gcd_bin(40902, 24140)</code> takes us about '''41''' usec
<code>gcd_bin(40902, 24140)</code> takes us about '''41''' usec

=={{header|Ruby}}==

That is already available as the ''gcd'' method of integers:
irb(main):001:0> require 'rational'
=> true
irb(main):002:0> 40902.gcd(24140)
=> 34

Here's an implementation:
<ruby>def gcd(u, v)
u, v = u.abs, v.abs
while v > 0
⚫
u, v = v, u % v
end
v
end</ruby>


=={{header|SETL}}==
=={{header|SETL}}==
Line 521: Line 529:
the gcd of 49865 and 69811 is 9973
the gcd of 49865 and 69811 is 9973
=={{header|Scheme}}==
=={{header|Scheme}}==
(define (gcd a b)
<scheme>(define (gcd a b)
(cond ((= a 0) b)
(cond ((= a 0) b)
((= b 0) a)
((= b 0) a)
((> a b) (gcd b (modulo a b)))
((> a b) (gcd b (modulo a b)))
(else (gcd a (modulo b a)))))
(else (gcd a (modulo b a)))))</scheme>


or using the standard function included with Scheme (takes any number of arguments):
or using the standard function included with Scheme (takes any number of arguments):
(gcd a b)
<scheme>(gcd a b)</scheme>


=={{header|TI-83 BASIC}}==
=={{header|TI-83 BASIC}}==

Revision as of 01:05, 22 December 2008

Task
Greatest common divisor
You are encouraged to solve this task according to the task description, using any language you may know.

This task requires the finding of the greatest common divisor of two integers.

Ada

<ada>with Ada.Text_Io; use Ada.Text_Io;

procedure Gcd_Test is 

  function Gcd (A, B : Integer) return Integer is
  begin
     if A = 0 then
        return B;
     end if;
     if B = 0 then
        return A;
     end if;
     if A > B then
        return Gcd(B, A mod B);
     else
        return Gcd(A, B mod A);
     end if;
  end Gcd;

begin 

  Put_Line("GCD of 100, 5 is" & Integer'Image(Gcd(100, 5)));
  Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100)));
  Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23)));

end Gcd_Test;</ada>

Output: 

GCD of 100, 5 is 5
GCD of 5, 100 is 5
GCD of 7, 23 is 1

ALGOL 68

PROC gcd = (INT a, b) INT: (
  IF a = 0 THEN
    b
  ELIF b = 0 THEN
    a
  ELIF a > b  THEN
    gcd(b, a MOD b)
  ELSE
    gcd(a, b MOD a)
  FI     
);

main : (
  INT a = 33, b = 77;
  printf(($x"The gcd of"g" and "g" is "gl$,a,b,gcd(a,b)));
  INT c = 49865, d = 69811;
  printf(($x"The gcd of"g" and "g" is "gl$,c,d,gcd(c,d)))
)

The output is: 

The gcd of        +33 and         +77 is         +11
The gcd of     +49865 and      +69811 is       +9973

APL

Works with: Dyalog APL
       33 49865 ∨ 77 69811 
11 9973

If you're interested in how you'd write GCD in Dyalog, if Dyalog didn't have a primitive for it, (i.e. using other algorithms mentioned on this page: iterative, recursive, binary recursive), see different ways to write GCD in Dyalog.

Works with: APL2
       ⌈/(^/0=A∘.|X)/A←⍳⌊/X←49865 69811 
9973

C

Iterative Euclid algorithm

<c>int gcd_iter(int u, int v) { 

 int t;
 while (v) {
   t = u; 
   u = v; 
   v = t % v;
 }
 return u < 0 ? -u : u; /* abs(u) */

}</c>

Recursive Euclid algorithm

<c>int gcd(int u, int v) { 

 if (v)
   return gcd(v, u % v);
 else 
   return u < 0 ? -u : u; /* abs(u) */

}</c>

Iterative binary algorithm

<c>int gcd_bin(int u, int v) { 

 int t, k;

 u = u < 0 ? -u : u; /* abs(u) */
 v = v < 0 ? -v : v; 
 if (u < v) {
   t = u;
   u = v;
   v = t;
 }
 if (v == 0)
   return u;

 k = 1;
 while (u & 1 == 0 && v & 1 == 0) { /* u, v - even */
   u >>= 1; v >>= 1;
   k <<= 1;
 }

 t = (u & 1) ? -v : u;
 while (t) {
   while (t & 1 == 0) 
     t >>= 1;

   if (t > 0)
     u = t;
   else
     v = -t;

   t = u - v;
 }
 return u * k;

}</c>

Notes on performance

gcd_iter(40902, 24140) takes us about 2.87 usec

gcd_bin(40902, 24140) takes us about 2.47 usec

gcd(40902, 24140) takes us about 2.86 usec

Forth

: gcd ( a b -- n )
  begin dup while tuck mod repeat drop ;

Fortran

Recursive Euclid algorithm

In ISO Fortran 95 or later, use RECURSIVE function: 

   recursive function gcd_rec(u, v) result(gcd)
       integer             :: gcd
       integer, intent(in) :: u, v
       
       if (mod(u, v) /= 0) then
           gcd = gcd_rec(v, mod(u, v))
       else
           gcd = v
       end if
   end function gcd_rec

Iterative Euclid algorithm

      subroutine gcd_iter(value, u, v)
Cf2py integer, intent(out) :: value
      integer value, u, v, t
      intrinsic abs, mod
C
      do while( v.NE.0 )
         t = u
         u = v
         v = mod(t, v)
      enddo
      value = abs(u)
      end subroutine gcd_iter

Iterative binary algorithm

      subroutine gcd_bin(value, u, v)
Cf2py integer, intent(out) :: value
      integer value, u, v, k, t, abs, mod
      intrinsic abs, mod
      u = abs(u)
      v = abs(v)
      if( u.lt.v ) then
         t = u
         u = v
         v = t
      endif
      if( v.eq.0 ) then
         value = u
         return
      endif
      k = 1
      do while( (mod(u, 2).eq.0).and.(mod(v, 2).eq.0) )
         u = u / 2
         v = v / 2
         k = k * 2
      enddo
      if( (mod(u, 2).eq.0) ) then
         t = u
      else
         t = -v
      endif
      do while( t.ne.0 )
         do while( (mod(t, 2).eq.0) )
            t = t / 2
         enddo
         if( t.gt.0 ) then
            u = t
         else
            v = -t
         endif
         t = u - v
      enddo
      value = u * k
      end subroutine gcd_bin

Notes on performance

gcd_iter(40902, 24140) takes us about 2.8 usec

gcd_bin(40902, 24140) takes us about 2.5 usec

Haskell

That is already available as the function gcd in the Prelude. Here's the implementation: 

gcd :: (Integral a) => a -> a -> a
gcd 0 0 =  error "Prelude.gcd: gcd 0 0 is undefined"
gcd x y =  gcd' (abs x) (abs y) where
  gcd' a 0  =  a
  gcd' a b  =  gcd' b (a `rem` b)

J

x+.y

Java

Iterative

<java>public static long gcd(long a, long b){ 

  long factor= Math.max(a, b);
  for(long loop= factor;loop > 1;loop--){
     if(a % loop == 0 && b % loop == 0){
        return loop;
     }
  }
  return 1;

}</java>

Recursive

<java>public static long gcd(long a, long b){ 

  if(a == 0) return b;
  if(b == 0) return a;
  if(a > b) return gcd(b, a % b);
  return gcd(a, b % a);

}</java>

Joy

gcd == [0 >] [dup rollup rem] while pop;


to gcd :a :b
  if :b = 0 [output :a]
  output gcd :b  modulo :a :b
end

Lucid

dataflow algorithm

gcd(n,m) where
   z = [% n, m %] fby if x > y then [% x - y, y %] else [% x, y - x%] fi;
   x = hd(z);
   y = hd(tl(z));
   gcd(n, m) = (x asa x*y eq 0) fby eod;
end

Mathematica

GCD[a, b]

MAXScript

Iterative Euclid algorithm

fn gcdIter a b =
(
    while b > 0 do
    (
        c = mod a b
        a = b
        b = c
    )
    abs a
)

Recursive Euclid algorithm

fn gcdRec a b =
(
    if b > 0 then gcdRec b (mod a b) else abs a
)

Nial

Nial provides gcd in the standard lib. 

|loaddefs 'niallib/gcd.ndf'
|gcd 6 4
=2

defining it for arrays 

# red is the reduction operator for a sorted list
# one is termination condition
red is cull filter (0 unequal) link [mod [rest, first] , first]
one is or [= [1 first, tally], > [2 first,  first]]
gcd is fork [one, first, gcd red] sort <=

Using it 

|gcd 9 6 3
=3

OCaml

<ocaml>let rec gcd a b = 

 if      a = 0 then b
 else if b = 0 then a
 else if a > b then gcd b (a mod b)
 else               gcd a (b mod a)</ocaml>

Pascal

<pascal>function gcd(a, b: integer): integer; 

var
 tmp: integer;
begin
 while b <> 0 do
  begin
   tmp := a mod b;
   a := b;
   b := tmp
  end;
 gcd := a
end;</pascal>

Perl

Iterative Euclid algorithm

<perl>sub gcd_iter($$) { 

 my ($u, $v) = @_;
 while ($v) {
   ($u, $v) = ($v, $u % $v);
 }
 return abs($u);

}</perl>

Recursive Euclid algorithm

<perl>sub gcd($$) { 

 my ($u, $v) = @_;
 if ($v) {
   return gcd($v, $u % $v);
 } else {
   return abs($u);
 }

}</perl>

Iterative binary algorithm

<perl>sub gcd_bin($$) { 

 my ($u, $v) = @_;
 $u = abs($u);
 $v = abs($v);
 if ($u < $v) {
   ($u, $v) = ($v, $u);
 }
 if ($v == 0) {
   return $u;
 }
 my $k = 1;
 while ($u & 1 == 0 && $v & 1 == 0) {
   $u >>= 1;
   $v >>= 1;
   $k <<= 1;
 }
 my $t = ($u & 1) ? -$v : $u;
 while ($t) {
   while ($t & 1 == 0) {
     $t >>= 1;
   }
   if ($t > 0) {
     $u = $t;
   } else {
     $v = -$t;
   }
   $t = $u - $v;
 }
 return $u * $k;

}</perl>

Notes on performance

<perl>use Benchmark qw(cmpthese);

my $u = 40902; my $v = 24140; cmpthese(-5, { 

 'gcd' => sub { gcd($u, $v); },
 'gcd_iter' => sub { gcd_iter($u, $v); },
 'gcd_bin' => sub { gcd_bin($u, $v); },

});</perl>

Output on 'Intel(R) Pentium(R) 4 CPU 1.50GHz' / Linux / Perl 5.8.8: 

             Rate  gcd_bin gcd_iter      gcd
gcd_bin  321639/s       --     -12%     -20%
gcd_iter 366890/s      14%       --      -9%
gcd      401149/s      25%       9%       --

Pop11

Built-in gcd

gcd_n(15, 12, 2) =>

Note: the last argument gives the number of other arguments (in this case 2).

Iterative Euclid algorithm

define gcd(k, l) -> r;
    lvars k , l, r = l;
    abs(k) -> k;
    abs(l) -> l;
    if k < l then (k, l) -> (l, k) endif;
    while l /= 0 do
        (l, k rem l) -> (k, l)
    endwhile;
    k -> r;
enddefine;

Prolog

Recursive Euclid Algorithm

gcd(X, 0, X).
gcd(0, X, X).
gcd(X, X, X).
gcd(X, Y, D) :- X > Y, Z is X mod Y, gcd(Y, Z, D).
gcd(X, Y, D) :- X < Y, Z is Y mod X, gcd(X, Z, D).

Repeated Subtraction

gcd(X, X, X).
gcd(X, Y, D) :- X < Y, Z is Y - X, gcd(X, Z, D).
gcd(X, Y, D) :- Y < X, gcd(Y, X, D).

Python

Iterative Euclid algorithm

<python>def gcd_iter(u, v): 

   while v:
       u, v = v, u % v
   return abs(u)</python>

Recursive Euclid algorithm

Interpreter: Python 2.5 <python>def gcd(u, v): 

   return gcd(v, u % v) if v else abs(u)</python>

Tests

>>> gcd(0,0)
0
>>> gcd(0, 10) == gcd(10, 0) == gcd(-10, 0) == gcd(0, -10) == 10
True
>>> gcd(9, 6) == gcd(6, 9) == gcd(-6, 9) == gcd(9, -6) == gcd(6, -9) == gcd(-9, 6) == 3
True
>>> gcd(8, 45) == gcd(45, 8) == gcd(-45, 8) == gcd(8, -45) == gcd(-8, 45) == gcd(45, -8) == 1
True
>>> gcd(40902, 24140) # check Knuth :)
34

Iterative binary algorithm

See The Art of Computer Programming by Knuth (Vol.2) <python>def gcd_bin(u, v): 

   u, v = abs(u), abs(v) # u >= 0, v >= 0
   if u < v:
       u, v = v, u # u >= v >= 0
   if v == 0:
       return u
  
   # u >= v > 0
   k = 1
   while u & 1 == 0 and v & 1 == 0: # u, v - even
       u >>= 1; v >>= 1
       k <<= 1
      
   t = -v if u & 1 else u
   while t:
       while t & 1 == 0:
           t >>= 1
       if t > 0:
           u = t
       else:
           v = -t
       t = u - v
   return u * k</python>

Notes on performance

gcd(40902, 24140) takes us about 17 usec

gcd_iter(40902, 24140) takes us about 11 usec

gcd_bin(40902, 24140) takes us about 41 usec

Ruby

That is already available as the gcd method of integers: 

irb(main):001:0> require 'rational'
=> true
irb(main):002:0> 40902.gcd(24140)
=> 34

Here's an implementation: def gcd(u, v) 

 u, v = u.abs, v.abs
 while v > 0
   u, v = v, u % v
 end
 v

end

SETL

a := 33; b := 77;
print(" the gcd of",a," and ",b," is ",gcd(a,b));

c := 49865; d := 69811;
print(" the gcd of",c," and ",d," is ",gcd(c,d));

procedure gcd(a, b);
  return if a = 0 then
    b
  elseif b = 0 then
    a
  elseif a > b  then
    gcd(b, a mod b)
  else
    gcd(a, b mod a)
  end if;
end gcd;

Output: 

the gcd of 33  and  77  is  11
the gcd of 49865  and  69811  is  9973

Scheme

<scheme>(define (gcd a b) 

 (cond ((= a 0) b)
       ((= b 0) a)
       ((> a b) (gcd b (modulo a b)))
       (else    (gcd a (modulo b a)))))</scheme>

or using the standard function included with Scheme (takes any number of arguments): <scheme>(gcd a b)</scheme>

TI-83 BASIC

gcd(A,B)

V

like joy

iterative

[gcd
   [0 >] [dup rollup %]
   while
   pop
].

recursive

like python 

[gcd
   [zero?] [pop]
      [swap [dup] dip swap %]
   tailrec].

same with view: (swap [dup] dip swap % is replaced with a destructuring view) 

[gcd
   [zero?] [pop]
     [[a b : [b a b %]] view i]
   tailrec].

running it 

|1071 1029 gcd
=21
Retrieved from "https://rosettacode.org/wiki/Greatest_common_divisor?oldid=51397"