【課題４−４】　提出課題（２）
ユークリッドの互除法を用いて２つの整数値の最大公約数を求める関数を，空欄Ａ〜Ｅを埋めて作成せよ．なお，ユークリッドの互除法とは，「m>nの整数値の最大公約数は，m-nとnの最大公約数を求める方法に置き換えることができる」というものである．

#include <stdio.h>

「　Ａ　」get_gcd(int m, int n);

int main(void) {
	int a, b, gcd;
	
	printf("Input two numbers: ");
	scanf("%d %d", &a, &b);
	
	gcd = get_gcd(a, b);
	printf("GCD of %d and %d is %d¥n", a, b, gcd);
	
	return 0;
}


// ユークリッドの互除法で最大公約数を求める
// 引数 m,n:整数値；　返値 最大公約数
「　Ｂ　」get_gcd(int m, int n)
{
	int tmp;
	
	while (n != 0) {		//割り切れるまでループ
		// mにnを代入．nにmをnで割ったあまりを代入
		tmp = m % n;
		「　Ｃ　」;
		「　　Ｄ　　」;
	}
	return 「　Ｅ　」;		//得られた最大公約数を返す
}	

【実行結果例】
	Input two numbers: 72 64
	GCD of 72 and 64 is 8

【解説とヒント】
ユークリッドの互除法を最も単純なアルゴリズムで用いると，
	while (m!=n) {
		if (m>n)
			m = m-n;
		else
			n = n-m;
	}
で得られるmが最大公約数になる．これでは効率が悪いので上のプログラムでは剰余を用いている．