0.5.6 Greatest Common Divisor, Least Common Multiple
The greatest common divisor of two integers, i and j, is the largest
integer that divides both i and j exactly. Likewise the least common
multiple of the same two integers is returns the smallest integer is
an even multiple of both i and j. The given implementation of the
greatest_common_div operation runs O(log m). Because the
least_common_mul operation calls greatest_common_div,
it, too, runs in logarithmic time. While these are not, in the
strictest sense, ``computer science'' algorithms they may be useful to
you nonetheless.
|
Search