利用辗转相除法——求最大公约数（详解）

╰+哭是因爲堅強的太久メ 2022-12-24 01:59 331阅读 0赞

## 辗转相除法 ##

求最大公约数：  
给定两个数，求这两个数的最大公约数

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

例如：假如需要求 100 和18 两个正整数的最大公约数,用欧几里得算法，是这样进行的：  
100 / 18 = 5 (余 10)  
18 / 10= 1(余8)  
10 / 8 = 1(余2)  
8 / 2 = 4 (余0)  
至此，最大公约数为2  
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 100 和 18 的最大公约数2。

//最大公约数
    //给定两个数，求这两个数的最大公约数
    #include<stdio.h>
    int Fac(int a, int b)
    { 
    	int d = 1;
    	int c = 0;
    	while (d)
    	{ 
    		c = a / b;
    		d = a % b;
    		a = b;
    		b = d;
    	}
    	return a;
    }
    int main()
    { 
    	int a = 0;
    	int b = 0;
    	int ret = 0;
    	printf("请输入两个数字：\n");
    	scanf("%d %d", &a, &b);
    	if (a>b)
    	{ 
    		ret=Fac(a, b);
    	}
    	else
    	{ 
    		ret = Fac(b, a);
    	}
    	printf("最大公约数：%d\n", ret);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center]  
辗转相除法求解最大公约数并不是唯一的方式，但是却相当简便！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/d363a6dc48e948a282bc1a60b6d7a065.png