AtCoderの攻略記事を調べていたところ『ユークリッドの互除法』という2 つの自然数の最大公約数を求める手法を知りました。どういう手法かというと以下のような内容です。

(問題) 1071 と 1029 の最大公約数を求める。

• 1071 を 1029 で割った余りは 42
• 1029 を 42 で割った余りは 21
• 42 を 21 で割った余りは 0

よって、最大公約数は21である。

という手法みたいです。ちなみに最古のアルゴリズムと言われているそうで、紀元前300年頃に考えられていたそうです。

面白そうなのでプログラムを考えてみることにしました。

プログラミングにあたり画面に2つの数字を入れてボタンを押すと答えが出るという感じにしたかったので今回はC++ではなくC#でwindows formで作ることにしました。

コード

ということでまずは画面を作ります。画面デザインとそれぞれの名前は以下のようにしました。

続いて計算ボタンを押した時のロジックです。

using System;
using System.Windows.Forms;

namespace EuclideanAlgorithm
{
    public partial class UserControl1: UserControl
    {
        public UserControl1()
        {
            InitializeComponent();
        }

        // 計算ボタンクリック
        private void calculationButton_Click(object sender, EventArgs e)
        {
            // 割る数
            int divisor = Math.Max(int.Parse(numberTextBox1.Text), int.Parse(numberTextBox2.Text));
            // 割られる数
            int dividend = Math.Min(int.Parse(numberTextBox1.Text), int.Parse(numberTextBox2.Text));

            while (true)
            {
                int quotient = divisor % dividend;

                if (quotient == 0)
                {
                    break;
                }

                divisor = dividend;
                dividend = quotient;
            }

            answerLabel.Text = dividend.ToString();
        }
    }
}

ソースは自分で考えてみたところ上記のようになりました。while(ture)でループを回していますが、ユークリッドの互除法を使うと最終的に余りがなくなり25行目のif文が通るかどうか不安です。

動かしてみると期待通りになっています。

その後他の人がどうプログラムを作っているのか見てみましたがループの条件に余りが0かどうかという判定をしていたので上記プログラムのif文は正しそうです。

さっと書いてあまり検証していないソースですが、こういう問題を解くのは楽しいですね。