本文共 910 字，大约阅读时间需要 3 分钟。

6-5 C程序设计 习题 7.7.2 辗转相除法求最大公约数 (4分)

题目

两个正整数的最大公约数（Greatest Common Divisor,GCD）是能够整除这两个整数的最大整数。请实现函数，用欧几里得算法（又叫辗转相除法）计算两个数的最大公约数。

欧几里得算法：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

例如，求252和105的最大公约数：

因为 252 % 105 = 147 ，所以252和105的最大公约数也就是147和105的最大公约数。

因为147 % 105 = 42，所以252和105的最大公约数，也就是147和105的最大公约数，也就是105和42的最大公约数，如此反复，最终可以得到21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

函数接口定义：

int Gcd(int a, int b);

其中，a和b是用户输入的两个正整数。

函数返回a和b的最大公约数。

如果a或b小于等于0，则函数返回-1。

裁判测试程序样例：

在这里给出函数被调用进行测试的例子：#include 
   
    int Gcd(int a, int b);int main(){
       int a, b, c;    scanf("%d %d", &a, &b);    c = Gcd(a,b);    if (c != -1)    {
           printf("%d\n", c);    }    else    {
           printf("Input number should be positive!\n");    }    return 0;}/* 请在这里填写答案 */
   

输入样例：

在这里给出一组输入。例如：

15 20

输出样例：

在这里给出相应的输出。例如：

5

源码：

int Gcd(int a, int b){
   	int t;		if(a<=0||b<=0){
   		return -1; }	if(a

转载地址：http://djnlf.baihongyu.com/