C的GCDfunction

问题1.问题5（可分割）我尝试了蛮力方法但是花了一些时间，所以我引用了几个站点并找到了这段代码：

#include int gcd(int a, int b) { while (b != 0) { a %= b; a ^= b; b ^= a; a ^= b; } return a; } int lcm(int a, int b) { return a / gcd(a, b) * b; } int main() { int res = 1; int i; for (i = 2; i <= 20; i++) { res = lcm(res, i); } printf("%d\n", res); return 0; } 

这很简单，但我不明白函数“gcd”是如何工作的; 有人可以帮我理解逻辑。 （我知道它返回2个数字的GCD，但为什么这么多操作呢？）

Answer 1

第二个问题：GCD函数使用Euclid算法 。 它计算A mod B ，然后用XOR交换交换A和B. 更易读的版本可能如下所示：

 int gcd(int a, int b) { int temp; while (b != 0) { temp = a % b; a = b; b = temp; } return a; } 

Answer 2

这个问题也可以通过递归以非常干净的方式解决：

 int gcd(int a, int b) { int remainder = a % b; if (remainder == 0) { return b; } return gcd(b, remainder); } 

Answer 3

我为GCD执行了这些陈述：

 #include #include int main(){ int l, s,r; printf("\n\tEnter value : "); scanf("%d %d",&l,&s); while(l%s!=0){ r=l%s; l=s; s=r; } printf("\n\tGCD = %d",s); getch(); } 

Answer 4

使用一点递归和Objective-C

 -(int)euclid:(int)numA numB:(int)numB { if (numB == 0) return numA; else return ([self euclid:numB numB:numA % numB]); }