最初に
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;
}