Justin's Words

求最大公约数算法

Posted on | In |

伪代码如下:

1
2
3
4
5
6
Algorithm gcd(integerOne, integerTwo)
    if (integerOne % integerTwo == 0)
        result = intergerTwo
    else
        result = gcd(integerTwo, integerOne % integerTwo)
    return result

C 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <Math.h>

int gcd(int n1, int n2)
{
    int nOne = fabs(n1);
    int nTwo = fabs(n2);

    if (nOne == 0) return nTwo;
    if (nTwo == 0) return nOne;

    int result;
    if (nOne % nTwo == 0)
        result = nTwo;
    else
        result = gcd(nTwo, nOne % nTwo);

    return result;
}