source: NonGTP/Boost/boost/pool/detail/gcd_lcm.hpp @ 857

Revision 857, 1.2 KB checked in by igarcia, 19 years ago (diff)
Line 
1// Copyright (C) 2000 Stephen Cleary
2//
3// Distributed under the Boost Software License, Version 1.0. (See
4// accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6//
7// See http://www.boost.org for updates, documentation, and revision history.
8
9#ifndef BOOST_POOL_GCD_LCM_HPP
10#define BOOST_POOL_GCD_LCM_HPP
11
12namespace boost {
13
14namespace details {
15namespace pool {
16
17// Greatest common divisor and least common multiple
18
19//
20// gcd is an algorithm that calculates the greatest common divisor of two
21//  integers, using Euclid's algorithm.
22//
23// Pre: A > 0 && B > 0
24// Recommended: A > B
25template <typename Integer>
26Integer gcd(Integer A, Integer B)
27{
28  do
29  {
30    const Integer tmp(B);
31    B = A % B;
32    A = tmp;
33  } while (B != 0);
34
35  return A;
36}
37
38//
39// lcm is an algorithm that calculates the least common multiple of two
40//  integers.
41//
42// Pre: A > 0 && B > 0
43// Recommended: A > B
44template <typename Integer>
45Integer lcm(const Integer & A, const Integer & B)
46{
47  Integer ret = A;
48  ret /= gcd(A, B);
49  ret *= B;
50  return ret;
51}
52
53} // namespace pool
54} // namespace details
55
56} // namespace boost
57
58#endif
Note: See TracBrowser for help on using the repository browser.