入力した2つの自然数の最大公約数を求める
当ページのリンクには広告が含まれています。
スポンサーリンク
入力した n個の整数から一番大きい数値を探すサンプルプログラムを紹介します。
ここでは「ユークリッドの互除法」を用いて、最大公約数を求めます。
ユークリッドの互除法
ユークリッドの互除法は、2つの自然数から最大公約数を求める手法のことです。
大きい自然数 a を小さい自然数 b で割った余りを r とすると、a と b の最大公約数は b と r の最大公約数に等しくなります。
プログラムでは次のようなアルゴリズムになります。
- 2つの自然数を入力
- a % b = r を計算
- b % r を計算
- 2. と 3. を r = 0 になるまで繰り返す
- b が最大公約数
サンプルプログラム
それではサンプルプログラムをみてみましょう。
/*
* C言語のサンプルプログラム - Webkaru
* - 入力した2つの自然数の最大公約数を求める -
*/
#include <stdio.h>
int main(void)
{
int a, b, r, tmp;
printf("2つの自然数を入力してください。\n");
printf("1つ目の自然数 = ");
scanf("%d", &a);
printf("2つ目の自然数 = ");
scanf("%d", &b);
/* 自然数 a > b を確認・入替 */
if(a<b){
tmp = a;
a = b;
b = tmp;
}
/* ユークリッドの互除法 */
r = a % b;
while(r!=0){
a = b;
b = r;
r = a % b;
}
/* 最大公約数を出力 */
printf("最大公約数 = %d\n", b);
return 0;
}
サンプルプログラムで使っている構文
実行結果
いくつかの実行結果です。
1つ目の自然数 = 3 2つ目の自然数 = 6 最大公約数 = 3
2つの自然数を入力してください。 1つ目の自然数 = 12 2つ目の自然数 = 4 最大公約数 = 4
2つの自然数を入力してください。 1つ目の自然数 = 72 2つ目の自然数 = 48 最大公約数 = 24
このように入力した n個の整数の中から一番大きい数を探して、出力します。