【C语言】求两个数的最大公约数（辗转相除、相减、穷举）

2024-07-12 22:30| 来源: 网络整理| 查看: 265

解题思路：

1、辗转相除法：先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数。

2、相减法：

取两个数中的较大的数做减数，较小的数做被减数，用大的数减去小数：如果结果为0，则被减数就是这两个数的最大公约数；如果结果不为0，则继续用这两个数中最大的数减较小的数，直到结果为0；则最大公约数为被减数。

3、穷举法：以较小的数为被除数分别和两个数做除法；被除数每做一次除法运算，值减少1，直到两个运算的余数都为0；则该被除数为这两个数的最大公约数。

具体代码：

1、辗转相除法：

#include #include int main(){ printf("请输入两个整数：\n"); int a; int b; int temp = 0; scanf_s("%d%d", &a, &b); if (a < b){ temp = a; a = b; b = temp; } while (a%b != 0){ temp = a%b; a = b; b = temp; } printf("最大公约数为：%d\n", b); system("pause"); return 0; }

运行结果：

2、相减法：

#include #include int main(){ printf("请输入两个整数：\n"); int a; int b; int temp = 0; scanf_s("%d%d", &a, &b); if (a < b){ temp = a; a = b; b = temp; } while (a-b!=0){ if (a < b){ temp = a; a = b; b = temp; } temp = a - b; a = b; b = temp; } printf("最大公约数为：%d\n", b); system("pause"); return 0; }

运行结果：

3、穷举法：

#include #include int main(){ printf("请输入两个整数：\n"); int a; int b; int temp = 0; scanf_s("%d%d", &a, &b); if (a < b){ temp = a; a = b; b = temp; } for (temp = b; a%temp || b%temp; temp--); printf("最大公约数为：%d\n", temp); system("pause"); return 0; }

运行结果：

【本文地址】

公司简介

联系我们