首页 > 代码库 > 最大公约数
最大公约数
最大公约数，根据《编程之美》递归版写的非递归版：
1. 对于y和x来说，如果y=k*y1, x = k * x1。那么有gcd(y,x)=k*gcd(y1, x1);
2. 如果x=p*x1, p是素数（质数），并且y%p != 0，那么gcd(x, y) = gcd(p * x1, y) = gcd(x1, y)。
1 int gcd(int x, int y) { 2 int a = x, b = y; 3 int factor = 0; 4 while (a != 0 && b != 0) { 5 if (a < b) { 6 swap(a, b); 7 } 8 if (a & 0x01 == 0) { 9 if (b & 0x01 == 0) {10 b >>= 1;11 factor++;12 } 13 a >>= 1;14 } else {15 if (b & 0x01 == 0) {16 b >>= 1;17 } else {18 a -= b;19 }20 } 21 }22 if (a == 0) return b << factor;23 if (b == 0) return a << factor;24 }
最大公约数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。