greatest-common-divisor - 不使用 GCD 方法查找互质数

Question

是否可以在不使用任何标准 GCD 算法的情况下知道两个给定的数字是否互质？我使用了欧几里得、二进制 GCD 和 Lehmer 算法。如果可能的话，建议一种比这些更快的方法。这两个数字可以大到 10^5，因此生成法雷序列也没有用。

Answer 1

您可能会发现这两个简单实现之一比您在评论中链接到的函数更快。它是 c# 代码，但应该很容易转换为 c 或 java。这些适用于 unsigned int，但为其他类型编写版本应该很简单。

public static uint Gcd(uint value1, uint value2) {
    while (value1 != 0) {
        uint t = value2 % value1;
        value2 = value1;
        value1 = t;
    }
    return value2;
}

public static uint GcdR(uint value1, uint value2) {
    return (value1 == 0) ? value2 : GcdR(value2 % value1, value1);
}

由于模运算符，它似乎会变慢，但至少在 C# 中，它比您链接的函数快两倍多(将其转换为 C# 后)。我发现第一个非递归版本稍微快一些。对于您正在使用的语言，您必须进行基准测试，看看是否比您现有的更快。使用 Gcd 的 IsCoprime 看起来像这样

public static bool IsCoprime(this uint value1, uint value2) {
    // 25% of possible pairings are even num to even num so handle them
    // with a bit twiddle that's much faster than GCD function. If they
    // are both even, then they can't be coprime (2 is common divisor).
    return ((((value1 | value2) & 1) != 0)
            && (Gcd(value1, value2) == 1));
}