C语言：给定两个数，求这两个数的最大公约数（新思路：辗转相除法）-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言：给定两个数，求这两个数的最大公约数（新思路：辗转相除法）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

从键盘输入两个数，求这两个数的最大公约数。

=========================================================================

思路一：普通方法

总体思路：

（一）. 生成相关变量；

从键盘输入两个数；

再使用三目操作符（条件操作符）找出较小值。

（二）. 使用 while循环，

在循环中设置 if条件判断语句，

用两数分别模以较小值，

能整除（没有余数）则较小值就是最大公约数，

不能整除（没有余数）则较小值自减1，

直到能整除，此时较小值就是最大公约数，

进行打印。

第一步：

（1）. 生成相关变量：

int m = 0; -- 接收从键盘输入的第一个数；

int n = 0; -- 接收从键盘输入的第二个数。

（2）. 从键盘输入两个数 -- scanf()函数。

（3）. 使用三目操作符（条件操作符）找出较小值赋给变量k：

int k = (m > n ? n : m);

实现代码：
#include <stdio.h>
int main()
{
	//生成相关变量：
	int m = 0; //接收从键盘输入的第一个数
	int n = 0; //接收从键盘输入的第二个数

	//从键盘输入两个数：
	scanf("%d %d", &m, &n);

	//使用 三目操作符（条件操作符）找出较小值赋给变量k
	int k = (m > n ? n : m); //也可以用if条件判断语句

	return 0;
}
实现图片：

第二步：

（1）. 使用 while循环；

（2）. 在循环中设置 if条件判断语句：

用两数分别模以较小值，

能整除则较小值就是最大公约数，

不能整除则较小值自减1，

直到能整除，此时较小值就是最大公约数，

进行打印。

实现代码：
#include <stdio.h>
int main()
{
	//生成相关变量：
	int m = 0; //接收从键盘输入的第一个数
	int n = 0; //接收从键盘输入的第二个数

	//从键盘输入两个数：
	scanf("%d %d", &m, &n);

	//使用 三目操作符（条件操作符）找出较小值赋给变量k
	int k = (m > n ? n : m); //也可以用if条件判断语句

	//使用while循环：
	while (1) //一直循环，知道找到最大公约数再break跳出循环
	{
		//在循环中设置 if条件判断语句：
		if (m % k ==0 && n % k ==0)//用两数分别 模以 较小值
		{
			//能整除 则 较小值 就是 最大公约数
			break;//break跳出循环后进行打印
		}

		k--;//不能整除则 较小值 自减，再次循环，直到两个数都能被较小值整除
	}

	//进行打印：
	printf("%d\n", k);

	return 0;
}
实现图片：

思路一：最终代码和实现效果

最终代码：

#include <stdio.h>
int main()
{
	//生成相关变量：
	int m = 0; //接收从键盘输入的第一个数
	int n = 0; //接收从键盘输入的第二个数

	//从键盘输入两个数：
	scanf("%d %d", &m, &n);

	//使用 三目操作符（条件操作符）找出较小值赋给变量k
	int k = (m > n ? n : m); //也可以用if条件判断语句

	//使用while循环：
	while (1) //一直循环，知道找到最大公约数再break跳出循环
	{
		//在循环中设置 if条件判断语句：
		if (m % k ==0 && n % k ==0)//用两数分别 模以 较小值
		{
			//能整除 则 较小值 就是 最大公约数
			break;//break跳出循环后进行打印
		}

		k--;//不能整除则 较小值 自减，再次循环，直到两个数都能被较小值整除
	}

	//进行打印：
	printf("%d\n", k);

	return 0;
}

实现效果：

C语言：给定两个数，求这两个数的最大公约数（新思路：辗转相除法）

=========================================================================

思路二：辗转相除法

总体思路：

（一）. 生成相关变量，从键盘输入两个数。

（二）. 使用while循环，配合辗转相除法找出最大公约数。





第一步：

（1）. 生成相关变量：

int m = 0; -- 接收第一个数；

int n = 0; -- 接收第二个数；

int k = 0; -- 存放使用辗转相除法后得到的余数。



（2）. 从键盘输入两个数 -- scanf()函数

实现代码：
#include <stdio.h>
int main()
{
	//生成相关变量：
	int m = 0; //接收从键盘输入的第一个数
	int n = 0; //接收从键盘输入的第二个数
	int k = 0; //存放使用 辗转相除法 后得到的 余数

	//从键盘输入两个数：
	scanf("%d %d", &m, &n);


	return 0;
}
实现图片：

第二步：

（1）. 使用 while循环，配合辗转相除法找出最大公约数。

（2）. 辗转相除法：

用第一个数模以第二个数（两数位置可调换）得到余数，

若余数不为0，则把第二个数的值赋给第一个数的值，余数赋给第二个数，

继续把第一个数（此时是第二个数的值）模以第二个数（此时是余数的值）

得到新的余数，

循环这些步骤，直到余数为0 ，此时第二个数为最大公约数。

（3）. 打印第二个数，即最大公约数。

实现代码：
#include <stdio.h>
int main()
{
	//生成相关变量：
	int m = 0; //接收从键盘输入的第一个数
	int n = 0; //接收从键盘输入的第二个数
	int k = 0; //存放使用 辗转相除法 后得到的 余数

	//从键盘输入两个数：
	scanf("%d %d", &m, &n);

	//使用 while循环 ，配合 辗转相除法 找出 最大公约数
	while (k = m % n) 
	//求余数，当余数为0后停止循环，此时，n为最大公约数
	{
		m = n; //第二个数的值 赋给 第一个数
		n = k; //余数 赋给 第二个数

		//赋值后再求余数，直到余数为0
	}

	//打印第二个数，即最大公约数
	printf("%d\n", n);

	return 0;
}
实现图片：

思路二：最终代码和实现效果

最终代码：

#include <stdio.h>
int main()
{
	//生成相关变量：
	int m = 0; //接收从键盘输入的第一个数
	int n = 0; //接收从键盘输入的第二个数
	int k = 0; //存放使用 辗转相除法 后得到的 余数

	//从键盘输入两个数：
	scanf("%d %d", &m, &n);

	//使用 while循环 ，配合 辗转相除法 找出 最大公约数
	while (k = m % n) 
	//求余数，当余数为0后停止循环，此时，n为最大公约数
	{
		m = n; //第二个数的值 赋给 第一个数
		n = k; //余数 赋给 第二个数

		//赋值后再求余数，直到余数为0
	}

	//打印第二个数，即最大公约数
	printf("%d\n", n);

	return 0;
}