View Subcategory
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.
python
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)
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)
from fractions import gcd
print gcd(8, 12)
print gcd(8, 12)
clojure
(defn gcd [a b]
(if (zero? b)
a
(recur b (mod b a))))
(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
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
