求两个正整数的最大公约数(三种方法) |
您所在的位置：网站首页 › python中如何求两个数的最大公约数 › 求两个正整数的最大公约数(三种方法) |
求两个正整数的最大公约数(三种方法)
|
方法一:辗转相除法
又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
#define _CRT_SECURE_NO_WARNINGS #include int main() { int a, b; int min,max,temp; printf("请输入两个数字:\n"); scanf("%d %d", &a, &b); min = a > b ? b : a; max = a > b ? a : b; while (max%min != 0) { temp = max%min; max = min; min = temp; } if (min == 1) { printf("这两个数互质."); } else { printf("这两个数字的最大公约数为:%d\n", min); } return 0; } 方法二:循环遍历 #define _CRT_SECURE_NO_WARNINGS #include int main() { int a, b; int min,max; printf("请输入两个正整数:\n"); scanf("%d %d", &a, &b); min = a < b ? a : b; for (int i = 2;i (7,14)，此时，7小于14，要做一次交换，把14作为被减数，即(14,7)->(7,7)，再做一次相减，结果为0，这样也就求出了最大公约数7 代码如下: #define _CRT_SECURE_NO_WARNINGS #include int main() { int a, b; int min, max; int temp; printf("请输入两个正整数:\n"); scanf("%d %d", &a, &b); min = a > b ? b : a; max = a > b ? a : b; while (max - min != 0) { temp = max - min; max = temp > min ? temp : min; min = temp > min ? min : temp; } printf("最大公约数是:%d\n", max); return 0; }以上只是本人拙见 多有纰漏望指出 ! |
【本文地址】
今日新闻 |
推荐新闻 |