最小公倍数アルゴリズム

1. 素因数の分解方法

まずこれらの数値の素因数を書き出します、最小公倍数はそのすべてに等しいです。素因数: の積 (複数の素因数が同じ場合、2 つの数値のどちらがより多くの素因数を持っているかを比較し、それらをより多く乗算します)。

たとえば、45 と 30 の最小公倍数を見つけます。

45=3*3*5

30=2*3*5

異なる素因数は 2、5、3 であり、これらは次の素因数です。因数、45 には 3 が 2 つあり、30 には 3 が 1 つしかないため、最小公倍数を計算するときは、2 つの 3 を掛けます。

2 つあるので、数値の積は、2 つの数値の最大公約数と最小公倍数の積に等しくなります。つまり、(a, b) × [a, b] = a × b となります。したがって、2 つの数値の最小公倍数を見つけるには、まずそれらの最大公約数を見つけてから、上記の公式を使用して最小公倍数を見つけることができます。

たとえば、[18, 20] を見つけた場合、[18, 20] = 18 × 20 ÷ (18, 20) = 18 × 20 ÷ 2 = 180 となります。複数の自然数の最小公倍数を見つけるには、まず 2 つの数値の最小公倍数を見つけ、次にこの最小公倍数と 3 番目の数値の最小公倍数を見つけ、続けて最後の 1 つを見つけます。最終的に得られる最小公倍数が、求めた数値の最小公倍数になります。

以上が最小公倍数アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。