langref.org - ruby, java, perl, groovy ... - Algorithms | Arithmetic

View Problem

Algorithms

Arithmetic

Greatest Common Divisor

Find the largest positive integer that divides two given numbers without a remainder. For example, the GCD of 8 and 12 is 4.

ruby 1.9.1

135.gcd(30)
# => 15

java

static int gcd(int a, int b) {
if (Math.min(a, b) == 0)
return Math.max(a, b);
else
return gcd(Math.min(a, b), Math.abs(a - b));
}

perl 5

sub gcd {
my ($a, $b) = @_;
($a,$b) = ($b,$a) if $a > $b;

while ($a) { ($a, $b) = ($b % $a, $a) }

return $b;
}

print gcd( 8, 12 );

perl

my $g = gcd (8, 12);
print $g;

sub gcd {
# Euclid's Algorithm - recursive
my ($c, $d) = @_;
return $c unless $d;
return gcd ($d, $c % $d);
}

perl

my $g = gcd2 (8, 12);
print $g;

sub gcd2 {
# Dijkstra's Algorithm - recursive
my ($c, $d) = @_;
return $c if $c == $d;
return $c > $d? gcd2 ($c - $d, $d) : gcd2 ($c, $d - $c);
}

groovy

static def gcd(int i, int j) {
if (Math.min(i,j)==0) return Math.max(i,j)
else return gcd(Math.min(i,j),Math.abs(i-j))
}

scala

def gcd(x: Int, y: Int): Int =
if (b == 0) x
else gcd(b, x % y)

python python 2.7

def gcd_recursive(i, j):
if min(i, j) == 0:
return max(i, j)
else:
return gcd_recursive(min(i, j), abs(i - j))

def gcd_iterative(i, j):
while min(i, j) != 0:
i, j = min(i, j), abs(i - j)
return max(i, j)

if __name__ == "__main__":
print gcd_recursive(8, 12)
print gcd_iterative(8, 12)

python 2.6+

from fractions import gcd
print gcd(8, 12)

cpp

#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

int gcd_recursive(int i, int j) {
if (min(i, j) == 0)
return max(i, j);
else
return gcd_recursive(min(i, j), abs(i - j));
}

int gcd_recursive2(int x, int y) {
if (y == 0)
return x;
else
return gcd_recursive2(y, (x % y));
}

int gcd_iterative(int i, int j) {
while (min(i, j) != 0) {
i = min(i, j);
j = abs(i - j);
}
return max(i, j);
}

int main() {
std::cout << gcd_recursive(8, 12) << std::endl;
std::cout << gcd_recursive2(8, 12) << std::endl;
std::cout << gcd_iterative(8, 12) << std::endl;
return 0;
}

fsharp

let rec gcd x y =
if y = 0 then x
else gcd y (x % y)

erlang

-module(gcd).
-export([gcd/2]).

gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).

ocaml

(* tail recursive *)
let rec gcd n m =
if m = 0 then
n
else if n > m then
gcd (n-m) m
else
gcd n (m-n)
;;

csharp

public static int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}

haskell

8 `gcd` 12

clojure

(defn gcd [a b]
(if (zero? b)
a
(recur b (mod b a))))

fantom

gcd := |Int a, Int b -> Int| {
pair := [a, b].sort
while (pair.first != 0)
pair.set(1, pair.last % pair.first).swap(0, 1)
return pair.last
}
echo(gcd(12, 8)) // a>b, result == 4
echo(gcd(1029, 1071)) // a<b, result == 21

Submit a new solution for ruby, java, perl, groovy ...