＜辗转相除法＞求最大公因数 C语言+超级奇妙配图讲解_辗转相除法求最大公因数c语言

作者：AllinToyou | 2024-06-02 11:51:37

踩

辗转相除法求最大公因数c语言

输入两个数 a、b，求这两个数的最大公因数

如果b等于0的话，计算结束，a就是最大公因数

如果b不等于0，那么就去计算 a 对 b 的余数 r ，之后将 a 取 b 的值，b 取 r 的值，再回到第一步直到b为0为止。

以 a=12，b=18 为例

接下来求 a 对 b 的余数 r ；并且将 b 的值赋予a，r 的值赋予 b ；

在重复上述过程，直到b的值是0；

综合图解，是可以看出是有规律可循的，表格中的值每一个值是自右向左依次传递的，a的值是右边的b传递的，b的值又是其右边的r传递的，r的值是a与b相除取余得到的，所以叫辗转相除法


int main(){
	int a,b;
	scanf("%d",&a);
	scanf("%d",&b);
	while(b!=0){
		int r=a%b;
		a=b;
		b=r;
	}
	printf("最大公因数是：%d",a);	
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/662593

＜辗转相除法＞ 求最大公因数 C语言+超级奇妙配图讲解_辗转相除法求最大公因数c语言