最大公倍数&最小公倍数:C++コード

最初に

C++で書かれた、最大公倍数と最小公倍数のサンプル。

表記

最小公倍数
gcd(a,b)
最大公倍数
lcm(a,b)

情報

wikipediaより最小公倍数
wikipediaより最大公倍数
海外サイトより、「最も効率的なGCD」より

C++コード

#include 

/**
* 最大公約数をa,bから求める
* @param [in] a 正整数
* @param [in] b 正整数
* @return 最大公約数
*/
template
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
TypeInt G_C_D(const std::vector &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
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
TypeInt L_C_M(const std::vector &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;
}

オンライン実行

コメント 

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください