什么是检查两个给定数字为互质的最快方法是什么？

Question

的一种方法是计算它们的 GCD 并检查它是否是1。

有一些更快的方法？

Answer 1

在欧几里德算法（计算gcd）是非常快的。当两个数均匀随机从[1, n]拉伸，以计算步骤的平均数目其gcd是O(log n)。对于每个步骤所需的平均计算时间是在的位数二次的。

有执行稍好（即，每一个步骤是在的位数次二次）的替代方案，但它们仅在非常大的整数有效。见，例如，在Schönhage的算法和次二次整数GCD计算。

Answer 2

如果你是一个机师哪/余数是显著比的变化更贵上运行，可以考虑二进制GCD 。