1

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

4

1 回答 1

3

您可能会发现这两个简单实现之一比您在评论中链接到的函数更快。它是 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));
}
于 2014-03-14T22:48:09.417 回答