[c言語]ユークリッドの互除法

C言語

これを聞いたことがない人はいないほど有名なユークリッド互除法。今日はそれをc言語を使って実装していきましょう。やっと本格的なプログラミングになってきましたね。では、早速始めていきましょう!

自然数xとyの最大公約数の計算の流れ

  1. xをyで割り、その余りのrに注目する。
  2. もしr=0なら、yが最大公約数であり、計算を終了する。
  3. yをrで割り、その余りr1に注目する。
  4. もしr1=0なら、rが最大公約数であり、計算を終了する。
  5. いか同様に計算をしていくと、rk=0となる。
  6. rk=0であるから、r(k-1)が最大公約数となり、計算を終了する。

例題がありますので、流れを確認しましょう。

ユークリッドの互除法をdo-while文で実装してみましょう!

さっきので計算の流れを簡単にイメージできたと思います。早速サンプルコードを見てみましょう。

#include <stdio.h>

int main(void){

  int a,b,r;

  printf("整数a: "); scanf("%d",&a);
  printf("整数b: "); scanf("%d",&b);

  do{
    r=a%b;
    a=b;
    b=r;
  }while(r!=0);
 
  printf("最大公約数は%dです\n",a);
}

/*実行結果
整数a: 128
整数b: 72
最大公約数は8です
*/

最初の1枚目はさっきの写真をまた載せました。

以下の二枚の写真が計算の流れになります。

少し見づらいかと思いますが、ご了承ください。

今回は高校時代に勉強したユークリッドの互除法を実装してみましたが、初めて自分がユークリッドの互除法を実装したときは身近な計算を実装できたことに感動を覚えました。これからこれまで勉強してきたものを実装していくと思いますが、楽しんで、感動を覚えながらやると上達するスピードが格段に早くなると思います。

以上で今回は終了となります。ありがとうございました!

コメント

タイトルとURLをコピーしました