最初に
C++で書かれた、最大公倍数と最小公倍数のサンプル。表記
最小公倍数gcd(a,b)
最大公倍数
lcm(a,b)
情報
wikipediaより最小公倍数wikipediaより最大公倍数
海外サイトより、「最も効率的なGCD」より
C++コード
#include <vector> /** * 最大公約数をa,bから求める * @param [in] a 正整数 * @param [in] b 正整数 * @return 最大公約数 */ template<typename TypeInt> TypeInt G_C_D(TypeInt a, TypeInt b) { if (a < 0) a = -a; if (b < 0) b = -b; while (b != 0) { a %= b; if (a == 0) return b; b %= a; } return a; } /** * 最大公約数をa,b,...から求める * @param [in] list 2つ以上の正整数 * @return 最大公約数 */ template<typename TypeInt> TypeInt G_C_D(const std::vector<TypeInt> &list) { if (list.size() < 2) throw "内容が1以下\n"; TypeInt a = list[0]; for (size_t i = 1; i < list.size(); ++i) { a = G_C_D(a, list[i]); } return a; } /** * 最小公約数をa,bから求める * @param [in] a 正整数 * @param [in] b 正整数 * @return 最小公約数 */ template<typename TypeInt> TypeInt L_C_M(TypeInt a, TypeInt b) { if( a == 0 && b == 0)return 0; return a / G_C_D(a, b) * b; } /** * 最小公約数をa,b,...から求める * @param [in] list 2つ以上の正整数 * @return 最小公約数 */ template<typename TypeInt> TypeInt L_C_M(const std::vector<TypeInt> &list) { if (list.size() < 2) throw "内容が1以下\n"; TypeInt a = list[0]; for (size_t i = 1; i < list.size(); ++i) { a = L_C_M(a, list[i]); } return a; }