用于 C 的 GCD 函数

Question

Q 1.问题 5（均匀可整除） 我尝试了蛮力方法，但需要时间，所以我参考了几个网站并找到了以下代码：

#include<stdio.h>
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("%dn", res);
    return 0;
}

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

Answer 1

对于你的第二个问题：GCD函数使用欧几里得算法。它计算A mod B，然后用异或交换交换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

C 语言中的 GCD 计算：

int gcd(int a, int b){
    if (a && b) for(;(a %= b) && (b %= a););
    return a | b;
}

绝对值计算：

#include <limits.h>
unsigned int abso(int v){
    const int mask = v >> (sizeof(int) * CHAR_BIT - 1);
    return (v + mask) ^ mask;
}

Answer 4

我为 GCD 执行了以下语句：

#include<stdio.h>
#include<conio.h>
int main(){
   int l, s,r;
   printf("ntEnter value : ");
   scanf("%d %d",&l,&s);
  while(l%s!=0){
    r=l%s;
    l=s;
    s=r;
  }
  printf("ntGCD = %d",s);
  getch();
}

Answer 5

使用一些递归和 Objective-C

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