// Copyright (C) 2000 Stephen Cleary | |
// | |
// Distributed under the Boost Software License, Version 1.0. (See | |
// accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
// | |
// See http://www.boost.org for updates, documentation, and revision history. | |
#ifndef BOOST_POOL_GCD_LCM_HPP | |
#define BOOST_POOL_GCD_LCM_HPP | |
namespace boost { | |
namespace details { | |
namespace pool { | |
// Greatest common divisor and least common multiple | |
// | |
// gcd is an algorithm that calculates the greatest common divisor of two | |
// integers, using Euclid's algorithm. | |
// | |
// Pre: A > 0 && B > 0 | |
// Recommended: A > B | |
template <typename Integer> | |
Integer gcd(Integer A, Integer B) | |
{ | |
do | |
{ | |
const Integer tmp(B); | |
B = A % B; | |
A = tmp; | |
} while (B != 0); | |
return A; | |
} | |
// | |
// lcm is an algorithm that calculates the least common multiple of two | |
// integers. | |
// | |
// Pre: A > 0 && B > 0 | |
// Recommended: A > B | |
template <typename Integer> | |
Integer lcm(const Integer & A, const Integer & B) | |
{ | |
Integer ret = A; | |
ret /= gcd(A, B); | |
ret *= B; | |
return ret; | |
} | |
} // namespace pool | |
} // namespace details | |
} // namespace boost | |
#endif |