View Problem
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
csharp
clojure
cpp
Submit a new solution for ruby, csharp, clojure, or cpp
There are 13 other solutions in additional languages (erlang, fantom, fsharp, groovy ...)
135.gcd(30)
# => 15
# => 15
public static int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
(defn gcd [a b]
(if (zero? b)
a
(recur b (mod b a))))
(if (zero? b)
a
(recur b (mod b a))))
#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;
}
#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;
}
Submit a new solution for ruby, csharp, clojure, or cpp
There are 13 other solutions in additional languages (erlang, fantom, fsharp, groovy ...)
