素因数分解 とは、素因数分解とは、整数をいくつかの素数の積に表すことです。つまり、割り切れない数字同士のかけ算で表すことです。ただし、「1」は省きます。
例えば、「28」を素因数分解すると、「28 = 2 * 2 * 7」となります。
「28」は偶数なのでまず「2」で割れます。「28 = 2 * 14」
でてきた「14」も偶数なので、もう一度「2」で割れます。「28 = 2 * 2 * 7」です。
素因数分解の手順としては、素因数分解したい数（上の例では「28」）を小さい素数から順に割っていきます。下図に「28」と「36」の素因数分解を示します。
この素因数分解ですが、最大公約数や最小公倍数の算出に利用できます。
ここで、最大公約数とは、0 ではない複数の整数の公約数のうち最大のものをさします。「G.C.D.（Greatest Common Divisor）」や「G.C.M.（Greatest Common Measure）」、「G.C.F.（Greatest Common Factor）」、「H.C.F.（Highest Common Factor）」とも表記されます。
また、最小公倍数とは、0 ではない複数の整数の公倍数のうち最小のものをさします。「L.C.M.（least common multiple）」とも表記されます。
最大公約数や最小公倍数を計算するには、通常は下図のように両方の数を同時に割ってゆきます。
共通に割った数字をかけたものが最大公約数であり、割った数字と割った結果の数字すべてを掛けたものが最小公倍数です。「28」と「36」の最大公約数は 2 × 2 = 4、最小公倍数は 2 × 2 × 7 × 9 = 252です。
ところで、この方法は、素因数分解の手順そのものですね。
ここで「28」と「36」を素因数分解してみます。
28 = 2 × 2 × 7
36 = 2 × 2 × 3 × 3
ここで、共通の素因数を掛け合わせると最大公約数が計算できます。
2 × 2 = 4
また、最大公約数に、残った数（この例では、「7」「3」「3」）をかけ合わせた数が最小公倍数です。
2 × 2 × 3 × 3 × 7 = 252
さて、汎用的には（ユークリッドの）互除法で最大公約数を算出する方法もあります。
二桁程度の数字同士であれば、2から素数で割っていってもいいのですが、桁数が大きくなると効率が悪いですね。その場合、ユークリッドの互除法を使うと効率的です。
(28, 36)
36 = 28 × 1 + 8
28 = 8 × 3 + 4
8 = 4 × 2
最後に割り切れたときの除数（「4」）が最大公約数です。
ここから、次のように最小公倍数を算出します。
28 × 36 / 4 = 252
gcd
アルゴリズム：最小公倍数と最大公約数を求めるjavascript - GameSprit
東京電力需給計
2011/5/22 13:00 ---------- 2957/3950万KW
75%
( 2011/5/22 14:30 UPDATE )
キーワード：数学、素因数分解、最大公約数、最小公倍数
例えば、「28」を素因数分解すると、「28 = 2 * 2 * 7」となります。
「28」は偶数なのでまず「2」で割れます。「28 = 2 * 14」
でてきた「14」も偶数なので、もう一度「2」で割れます。「28 = 2 * 2 * 7」です。
素因数分解の手順としては、素因数分解したい数（上の例では「28」）を小さい素数から順に割っていきます。下図に「28」と「36」の素因数分解を示します。
この素因数分解ですが、最大公約数や最小公倍数の算出に利用できます。
ここで、最大公約数とは、0 ではない複数の整数の公約数のうち最大のものをさします。「G.C.D.（Greatest Common Divisor）」や「G.C.M.（Greatest Common Measure）」、「G.C.F.（Greatest Common Factor）」、「H.C.F.（Highest Common Factor）」とも表記されます。
また、最小公倍数とは、0 ではない複数の整数の公倍数のうち最小のものをさします。「L.C.M.（least common multiple）」とも表記されます。
最大公約数や最小公倍数を計算するには、通常は下図のように両方の数を同時に割ってゆきます。
共通に割った数字をかけたものが最大公約数であり、割った数字と割った結果の数字すべてを掛けたものが最小公倍数です。「28」と「36」の最大公約数は 2 × 2 = 4、最小公倍数は 2 × 2 × 7 × 9 = 252です。
ところで、この方法は、素因数分解の手順そのものですね。
ここで「28」と「36」を素因数分解してみます。
28 = 2 × 2 × 7
36 = 2 × 2 × 3 × 3
ここで、共通の素因数を掛け合わせると最大公約数が計算できます。
2 × 2 = 4
また、最大公約数に、残った数（この例では、「7」「3」「3」）をかけ合わせた数が最小公倍数です。
2 × 2 × 3 × 3 × 7 = 252
さて、汎用的には（ユークリッドの）互除法で最大公約数を算出する方法もあります。
二桁程度の数字同士であれば、2から素数で割っていってもいいのですが、桁数が大きくなると効率が悪いですね。その場合、ユークリッドの互除法を使うと効率的です。
(28, 36)
36 = 28 × 1 + 8
28 = 8 × 3 + 4
8 = 4 × 2
最後に割り切れたときの除数（「4」）が最大公約数です。
ここから、次のように最小公倍数を算出します。
28 × 36 / 4 = 252
gcd
アルゴリズム：最小公倍数と最大公約数を求めるjavascript - GameSprit
東京電力需給計
2011/5/22 13:00 ---------- 2957/3950万KW
75%( 2011/5/22 14:30 UPDATE )
キーワード：数学、素因数分解、最大公約数、最小公倍数
