1. 全栈程序员必看首页

求最大公约数（C语言实现)

全栈程序员-站长 • • 未分类 • 阅读 3

求最大公约数（C语言实现)求最大公约数有多种方法 接下来我对辗转相除法 更相减损法分别做介绍 辗转相除法 gcd a b gcd b amodb 假如 需要求 1997 和 615 两个正整数的最大公约数 用辗转相除法 是这样进行的 1997 615 3 余 152 615 152 4 余 7 152 7 21 余 5 7 5 1 余 2 5 2 2 余 1 2 1 2 余 0 至此 最大公约数为 1 以除数和余数反复做除法运算 当余数为 0 时 取当前算式

求最大公约数有多种方法，接下来我对辗转相除法、更相减损法分别做介绍。

辗转相除法： gcd(a,b) = gcd(b,a mod b)。

更相减损法：

代码实现如下：

#include 
     //辗转相除法 int gcd1(int x, int y) { 
    //判断x/y余数是否为0 int z = x % y; //直到余数为0，则跳出循环 while(z) { 
    //循环过程中，将除数给x，余数给y，求新的余数z x = y; y = z; z = x % y; } //除数y为最大公约数 return y; } //更相减损术 int gcd2(int x, int y) { 
    int sum1 = 1; //先判断 x y是否都是偶数 while ((x % 2 == 0) && (y % 2 == 0)) { 
    sum1 *= 2; x = x / 2; y = y / 2; } while (1) { 
    //保证，被减数大于减数，不然就交换顺序 if (x < y) { 
    int temp = x; x = y; y = temp; } //差放在s中 int s = x - y; //判断差 和 减数 是否相等，如果是，跳出循环。 if (y == s) break; else { 
    x = y; y = s; } } //最大公约数就是约掉的若干个2的积与第二步中等数（减数=差）的乘积 return y * sum1; } int main() { 
    int a = 98; int b = 63; int max1 = gcd1(a, b); int max2 = gcd2(a, b); printf("%d %d的最大公约数为 %d\n", a, b, max1); printf("%d %d的最大公约数为 %d\n", a, b, max2); return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/221389.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月17日 下午6:13
下一篇 2026年3月17日 下午6:13


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号