今回は最小公倍数を計算するプログラムを作成します。
突然ですが、分数の足し算は好きですか？
足し算よりもかけ算のほうが普通は難しいのですが、分数の場合はそうではありません。分数のかけ算は分母同士、分子同士を掛け合わせるだけです。ところが分数の足し算は通分という作業が必要です。当時小学生だった私はこれがとても嫌だったのです。
通分するときは分母を計算しようとしている分母の最小公倍数にしなければなりません。2と3の最小公倍数であれば6であることはすぐにわかるのですが、14と18の最小公倍数なんていわれるとすぐには計算できません。
14の倍数：14, 28, 42, 56, 70, 84, 98, 112, 126, 140,
18の倍数：18, 36, 54, 72, 90, 108, 126, 144, 162, 180,
だから答えは126。教科書どおりやろうとするとこうなります。
もっと効率よく計算する方法はないのでしょうか？ この方法を教えてくれるのは中学1年生になってからです。簡単な方法だったので、どうして小学校で教えてくれないのかと怒りでいっぱいになったことがあります（ちょっと大袈裟か）。
効率が悪い最小公倍数をもとめるプログラム
まずは効率が悪い方法から紹介します。
14の倍数をリストに格納しておき、そのなかから18の倍数を探すというやり方です。最初にリストに格納すべき個数ですが、以下のように考えます。
14×18は最小ではないけれども14と18の公倍数である（14×18は14の18倍であり18の14倍だから）
そこで14×18以下の14の倍数を取得する
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Program { static void Main() { int a = 14; int b = 18; List<int> vs = new List<int>(); for (int i = 1; a * i <= a * b; i++) vs.Add(a * i); int answer = 0; foreach (int i in vs) { if (i % b == 0) { answer = i; Console.WriteLine(i); break; } } Console.WriteLine(answer); } } |
このやり方は効率が悪いです。14と18という比較的小さな数なのですぐに処理は終わりますが、巨大な数でしかも互いに素である場合、無駄に計算させられるだけでなく、それだけ多くの個数の倍数をリストに格納しなければならないのでメモリーも浪費することになります。
最小公倍数を求める
そこで中学校1年生のときに数学で教えてもらった方法を使います。
14, 18はともに素数2で割り切れる。2で割ると7と9
7と9は互いに素である。
2と7と9を掛け合わせた126が最小公倍数
素数2で割ると一発で終わってしまったので別の例を示します。
48 と 64 の最小公倍数を考える
48 と 64 はともに素数2で割り切れる。2で割ると 24 と 32
24 と 32 はともに素数2で割り切れる。2で割ると 12 と 16
12 と 16 はともに素数2で割り切れる。2で割ると 6 と 8
6 と 8はともに素数2で割り切れる。2で割ると 3 と 4
3 と 4 は互いに素である。
2 と 2 と 2 と 2 と 3 と 4 を掛け合わせた 192 が 48と64の最小公倍数である
割るときは最小の素数からやらないといけないわけではありません。両方とも16の倍数であることに気づいたのであれば
48 と 64 はともに16で割り切れる。16で割ると 3 と 4
3 と 4 は互いに素である。
16 と 3 と 4 を掛け合わせた 192 が48と64の最小公倍数である
こっちのほうがよいです。
また3つ以上の場合は以下のようにします。
14 と 48 と 64 との最小公倍数を考える
14 と 48 と 64 はともに2で割り切れる。2で割ると 7 と 24 と 32
24 と 32 は 8 で割り切れる。割り切れるものだけ8で割ると 7 と 3 と 4
これ以上、2つ以上の数を割りきることができる数は存在しない
2 と 8 と 7 と 3 と 4 を掛け合わせた 1344 が 14と48と64との最小公倍数である
ではこの方法でプログラミングしてみることにします。
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { Console.WriteLine("複数の2以上の自然数を半角スペースで区切って入力してください"); try { int[] vs = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray(); Console.WriteLine(GetLeastCommonMultiple(vs)); } catch { Console.WriteLine("不正な入力です"); } } static int GetLeastCommonMultiple(int[] vs) { // 1や0、負数は取り除く // その結果、配列の長さが2に満たない場合は例外を投げる vs = vs.Where(x => x > 1).ToArray(); if (vs.Length < 2) throw new Exception(); int div = 2; // 最初は2で割れるかを調べる List<int> divs = new List<int>(); while (true) { // ふたつ以上の数がdivで割り切ることができるなら割り切れるものだけ割る // 割り切ることができない場合はdivをインクリメントする // それによって2番目に大きな数よりもdivのほうが大きくなったとき // 割り切ることができる数は今後見つからないと判断してループを抜ける if (vs.Count(x => x % div == 0) > 1) { var a = vs.Where(x => x % div == 0).Select(x => x / div); var b = vs.Where(x => x % div != 0); vs = a.Union(b).ToArray(); divs.Add(div); } else div++; // 2番目に大きな数を取得する // そのためにソートして最後から2番目の要素を取得する Array.Sort(vs); if (vs[vs.Length - 2] < div) break; } int answer = 1; foreach (int i in divs) answer *= i; foreach (int i in vs) answer *= i; return answer; } } |
最大公約数を求める
最大公約数を求めるプログラムも作成してみることにします。3つ以上の最大公約数を求める場合はすべての数を割りきることができる数を探して割りきることができた数をすべて掛け合わせます。
48 と 64 と 108 の最大公約数を考える
48 と 64 と 108 はすべて 2 で割り切れる。2で割ると 24 と 32 と 54
24 と 32 と 54 はすべて 2 で割り切れる。2で割ると 12 と 16 と 27
これ以上、すべての数を割りきることができる数は存在しない
2 と 2 を掛け合わせた 4 が 48 と 64 と 108 の最大公約数である
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 |
class Program { static void Main() { Console.WriteLine("複数の2以上の自然数を半角スペースで区切って入力してください"); try { int[] vs = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray(); Console.WriteLine(GetGreatestCommonDivisor(vs)); } catch { Console.WriteLine("不正な入力です"); } } static int GetGreatestCommonDivisor(int[] vs) { // 配列の長さが2に満たない場合や0または負数が含まれている場合は例外を投げる if (vs.Length < 2 || vs.Count(x => x < 1) > 0) throw new Exception(); int div = 2; List<int> divs = new List<int>(); while (true) { if (vs.Count(x => x % div == 0) == vs.Length) { vs = vs.Select(x => x / div).ToArray(); divs.Add(div); } else div++; Array.Sort(vs); if (vs[vs.Length - 2] < div) break; } int answer = 1; foreach (int i in divs) answer *= i; return answer; } } |
鳩でも分かるC#管理人からのお願い
できる仕事であれば請け負います。鳩でもわかるC#管理人はクラウドワークスに在宅ワーカーとして登録しています。お仕事の依頼もお待ちしております。
⇒ 仕事を依頼する
コメントについて
コメントで英語などの外国語でコメントをされる方がいますが、管理人は日本語以外はわからないので基本的に内容が理解できず、承認することもありません。それからへんな薬を売っているサイトやリンク先のサイトが存在しないというスパムコメントも多々あります。
Some people make comments in foreign languages such as English, but since the manager does not understand anything other than Japanese, he basically cannot understand the content and does not approve it. Please use Japanese when making comments.
そんななか日本語のコメントもいただけるようになりました。「○○という変数はどこで宣言されているのか？」「××というメソッドはどこにあるのか」「例外が発生する」「いっそのことソース丸ごとくれ」という質問ですが、管理人としては嬉しく思います。「自分が書いた記事は読まれているんだな」と。疑問点には可能な限り答えます。記事に問題があれば修正いたします。
そのうえでお願いがあります。「匿名」という味も素っ気もない名前ではなく、捨てハンでいいのでなにかハンドルネームをつくってほしいと思います。
管理人のモチベーションアップのために
よろしければご支援お願いします。
⇒ 管理人の物乞いリスト
