1/15
Loading...
📘最大公約数 = 最も大きい共通約数
GCDは両方の数を割り切れる最大の数です。 例: 12と18の約数を列挙しましょう • 12の約数: 1, 2, 3, 4, 6, 12 • 18の約数: 1, 2, 3, 6, 9, 18 共通約数: 1, 2, 3, 6 → 最大は？ 6! よって GCD(12, 18) = 6
Loading...
GCDは両方の数を割り切れる最大の数です。 例: 12と18の約数を列挙しましょう • 12の約数: 1, 2, 3, 4, 6, 12 • 18の約数: 1, 2, 3, 6, 9, 18 共通約数: 1, 2, 3, 6 → 最大は？ 6! よって GCD(12, 18) = 6
ユークリッドの互除法は2000年以上の歴史を持つアルゴリズムで、2つの整数の最大公約数(GCD)を効率的に求めます。割り算の余りを使って繰り返し計算し、GCDがわかればLCMも簡単に計算できます。