[C++]Modern C++チャレンジの問題を解く～３問目～

最小公倍数とは

最小公倍数（さいしょうこうばいすう、英: least common multiple）とは、
0ではない複数の整数の公倍数のうち最小の自然数をさす。
たびたび、L.C.M.やlcm等の省略形で記述される。

最小公倍数 – Wikipedia

　最小公倍数の求め方は人が求めるのであれば総当たり、足りないものを考える、筆算、素因数分解、
など4通りほどあるらしいが、どれもプログラミングするのは難しい概念だ。

少なくとも筆者は解けなかった。

　正の整数2個の場合は以下の関係が成り立つパターンを求めればいいだろうが、
3個以上の正の整数の場合は別の解を求めるプログラムが必要だろう。

正整数a, bに対して、aとbの最大公約数 gcd(a, b)と最小公倍数lcm(a, b)との間には
gcd (a, b) ・ lcm (a, b) = ab
という関係がある。

最小公倍数 – Wikipedia

// [問題２]最大公約数を求める
unsigned int gcd(const unsigned int a, const unsigned int b)
{
	return (b == 0) ? a : gcd(b, a % b);
}

// 最小公倍数を求める
unsigned int lcm(unsigned int const a, unsigned int const b)
{
	unsigned int h = gcd(a, b);
	return h ? (a * (b / h)) : 0;
}

3つ以上の整数の最小公倍数を計算するには、ヘッダ<numeric>で定義されているstd::accumulateアルゴリズムが使えるそうだ。

// 3つ以上の整数の最小公倍数を計算するには、ヘッダ<numeric>で定義されているstd::accumulateアルゴリズムが使えます。
template<class InputIt>
int lcmr(InputIt first, InputIt last)
{
	return std::accumulate(first, last, 1, lcm);
}

2つ以上の0ではない整数の最小公倍数（lcm：least common multiple）は
英語でlowest common multiple、またはsmallest common multipleとも呼びますが、
それらすべての数で割り切れる最小の正の整数です。
最小公倍数を計算する1つの方法は、最大公約数の問題に帰着させることです。
次の公式が成り立ちます。

lcm(a, b) = abs(a*b) / gcd(a, b)

// [問題２]最大公約数を求める
unsigned int gcd(const unsigned int a, const unsigned int b)
{
	return (b == 0) ? a : gcd(b, a % b);
}

// 最小公倍数を求める
unsigned int lcm(unsigned int const a, unsigned int const b)
{
	unsigned int h = gcd(a, b);
	return h ? (a * (b / h)) : 0;
}

3つ以上の整数の最小公倍数を計算するには、
ヘッダ<numeric>で定義されているstd::accumulateアルゴリズムが使えるそうだ。

// 3つ以上の整数の最小公倍数を計算するには、ヘッダ<numeric>で定義されているstd::accumulateアルゴリズムが使えます。
template<class InputIt>
int lcmr(InputIt first, InputIt last)
{
	return std::accumulate(first, last, 1, lcm);
}

また、C++17には、ヘッダ<numeric>の中に、2つの数の最小公倍数を計算するconstexpr関数lcm()があるらしい。

https://cpprefjp.github.io/reference/numeric/lcm.html

補足説明

なお、実際に実行した結果が下図の通りである。
おそらく3つ以上の整数の最小公倍数を求める場合、
先に2つの整数の最小公倍数を計算し、その値と3つ目の整数の最小公倍数を求めるのだろう。
4つ目以降も同様の考え方で演算できる。

下図は、整数42、72、180の最小公倍数を求めた結果である。
最小公倍数の値が 2520 になっていることが確認できる。
最小公倍数を計算するサイトで検証してみたが、同じ値になるため計算が合っていることがわかる。