【C#】ユークリッドの互除法をプログラミングしました

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

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

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

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

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

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

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

 

コード


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

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

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

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

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

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

スポンサーリンク