C语言的GCD函数

Question

问题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("%d\n", res);
    return 0;
}

这很简单，但我不理解函数"gcd"是如何工作的。能否有人帮助我理解其逻辑呢？（我知道它返回两个数字的最大公约数，但为什么需要那么多操作呢？）

- Faizaan Mohammed

---

欢迎来到 Stack Overflow！如果您自己尝试解决问题并描述您尝试过的内容，我们更有可能能够帮助您。这样做还可以让您更多地学习 - 毕竟，您的目标是学习 C，对吧？ :) 祝您好运和编码愉快！ - Christian Ternus

在谷歌上搜索“Eratosthenes筛法”可以得到很多解释它的网站。如果你的搜索引擎没有相应结果，那么是时候换一个搜索引擎了。 - Jonathan Leffler

欢迎来到StackOverflow。该网站的设计理念是每个帖子只涉及一个问题。您明显提出了三个完全不同的问题（一个关于问题7，一个关于问题5，以及一个关于埃拉托斯特尼筛法）。请[编辑]您的问题并删除其中两个；您可以编写单独的帖子，并在那里分别提出其他问题。在您编辑时，您还可以将主题更改为有用的内容。对于未来的搜索，“Project Euler doubts”毫无意义。如果需要，[help]和[about]页面提供有关SO工作方式的更多信息。谢谢。 :-) - Ken White

这是求最大公约数的有趣代码。3个异或操作交换了a和b，但写起来更容易：`int gcd(int x, int y) { int r; if (x <= 0 || y <= 0) return(0); while ((r = x % y) != 0) { x = y; y = r; } return(y); }` 是的，它使用了一个局部变量，而你找到的代码没有使用，但这并不是一个显著的代价。我注意到至少还有两个关于欧拉计划5的问题（Euler Project 5 和 Euler Project 5）。 - Jonathan Leffler

http://rosettacode.org/wiki/Greatest_common_divisor#C - Adam

Answer 1

回答你的第二个问题：GCD函数使用欧几里得算法。 它计算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;
}

- Jack

Answer 2

这个问题也可以用递归的方式非常简洁地解决：

int gcd(int a, int b) {
    int remainder = a % b;

    if (remainder == 0) {
        return b;
    }

    return gcd(b, remainder);
}

- user427390

---

滥用递归的一种表现形式是将其写成一个简单的循环，这样的递归解法是不好的。 - Chris Taylor

这是非常干净的解决方案，比被接受的答案更易懂。点赞！ - Yahya

@ChrisTaylor 任何递归函数都可以写成循环，你的意思是我们根本不应该使用递归吗？ - Nikita Hismatov

@NikitaHismatov - 我并不反对使用递归，但单纯为了递归而递归就是存在问题的地方。有些问题非常适合用递归解决，这样使用很有意义；然而如果除了教学目的外，生产系统通常不会以递归方式实现的话，那么这种方法就没有必要。 - Chris Taylor

@ChrisTaylor 实际上，对于生产环境来说，这是可以接受的，因为它是尾递归，并且会被任何优化编译器转化为循环。事实上，代码非常清晰易懂，容易验证，这甚至可能使其成为生产系统中更可取的选择。 - Mark Adler

Answer 3

C语言中的最大公约数计算：

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;
}

- Michel

---

不要自己编写 abs 函数。为什么不直接使用标准库中的 abs 函数呢？ - undefined

Answer 4

我执行了这个求最大公约数的语句：

#include<stdio.h>
#include<conio.h>
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();
}

- Omar Faruk

Answer 5

使用一点递归和Objective-C

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

- Trygve