南郵編程在線編程題十三：最大公約數 -开发者知识库

題目轉自南郵編程在線：njupt.housecode.cc

實現求兩個正整數的最大公約數。

說明：（1）從鍵盤輸入兩個正整數；

（2）輸出這兩個正整數的最大公約數；

測試用例：輸入	測試用例：輸出
345 258< 回車 >	gcd=3
33 33< 回車 >	gcd=33
24 72< 回車 >	gcd=24

代碼如下：

#include <stdio.h>
int main()
{
	int a, b, r = 1, gcd;
	scanf("%d%d", &a, &b);
	while(r != 0){             //使用輾轉相除法求最大公約數 
		if(b > a){
			int i = b;
			b = a;
			a = i;
		}
		gcd = b;
		r = a % b;
		a = b;
		b = r;
	}
	printf("gcd=%d", gcd);
	return 0;
}

本題考察了while循環語句和求最大公約數的輾轉相除法（歐幾里得算法）

最佳答案：