10033 / 12877を約分せよ！ 分子と分母を10033と12877の最大公約数で割ればいいのですが、すぐにはわかりません。
2つの整数 A , B の最大公約数を高速に求めるアルゴリズムとして、ユークリッドの互除法があります。
1. A , B のうち小さい方で大きい方をわり、大きい方をその余りで置き換える
2. A , B のうち、いずれかが 0 の場合は終了。そうでない場合は 1 を繰り返す
3. 0 でない方の数がA , B の最大公約数になっている。
ユークリッドの互除法を使えば10033と12877の最大公約数は79であることがわかります。なので10033 / 12877を約分すると127 / 237になります。
また最小公倍数はAとBを掛けて最大公約数で割ると求めることができます。
C#で実装する
これをC#で実装してみることにします。AとBの双方がint型の範囲内であっても最小公倍数はこれを超える場合があります。またあとのことを考えてGetGCDメソッドとGetLCMメソッドの引数をlong型にしています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
using System; public class Program { static void Main() { int a = 12; int b = 16; long gcd = GetGCD(a, b); long lcm = GetLCM(a, b); Console.WriteLine($"{a}と{b}の最大公約数は{gcd}, 最小公倍数は{lcm}です"); } static long GetGCD(long a, long b) { while (a > 0 && b > 0) { if (a < b) b %= a; else a %= b; } return Math.Max(a, b); } static long GetLCM(long a, long b) { return a * b / GetGCD(a, b); } } |
実行結果
3つ以上の最大公約数と最小公倍数
3つ以上の整数a , b , c , d , e , … の場合はどうすればいいでしょうか？ まずaとbの最大公約数を求め、これとcの最大公約数を求める、そのあとこれとdの最大公約数を求める…を繰り返すことで求めることができます。また最小公倍数も同じ方法で求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
using System; public class Program { static void Main() { int[] ints = { 12, 16, 18 }; long gcd = GetGCD(ints[0], ints[1]); long lcm = GetLCM(ints[0], ints[1]); for (int i = 2; i < ints.Length; i++) { gcd = GetGCD(gcd, ints[i]); lcm = GetLCM(lcm, ints[i]); } Console.WriteLine($"{string.Join(", ", ints)}の最大公約数は{gcd}, 最小公倍数は{lcm}です"); } } |
実行結果
JavaScriptでも実装してみる
JavaScriptでも実装してみます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>鳩でもわかる最大公約数と最小公倍数</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> </head> <body> <p>ユークリッドの互除法で最大公約数と最小公倍数を求めます。</p> <p>2つ以上の整数を半角スペース区切りで入力してください。</p> <p><input type="text" id = "values"></p> <p><button onclick="calc()">計算</button></p> <p id = "result"></p> <script> function calc(){ const $result = document.getElementById('result'); const text = document.getElementById('values').value; if(text == ''){ $result.innerHTML = `なにも入力されていません`; return; } const arr = text.split(' '); const numbers = []; for(let i=0; i<arr.length; i++){ if(arr[i] == '') continue; const num = Number(arr[i]); if(Number.isInteger(num)) numbers.push(num); else { $result.innerHTML = `入力が不正です。${arr[i]}は整数ではありません`; return; } } let gcd = getGCD(numbers[0], numbers[1]); let lcm = getLCM(numbers[0], numbers[1]); for (let i = 2; i < numbers.length; i++){ gcd = getGCD(gcd, numbers[i]); lcm = getLCM(lcm, numbers[i]); } $result.innerHTML = `${numbers.join(', ')}の最大公約数は${gcd}, 最小公倍数は${lcm}です`; } function getGCD(a, b){ while (a > 0 && b > 0) { if (a < b) b %= a; else a %= b; } return Math.max(a, b); } function getLCM(a, b){ return a * b / getGCD(a, b); } </script> </body> </html> |
