一种方法是计算它们的gcd并检查它是否为 1。
有更快的方法吗？
问问题
12985 次
2 回答
12
欧几里得算法（计算gcd）非常快。当从 中均匀随机抽取两个数时[1, n]，计算它们的平均步数gcd为O(log n)。每一步所需的平均计算时间是位数的二次方。
有一些替代方案的性能要好一些（即，每个步骤的位数都是次二次的），但它们只对非常大的整数有效。例如，参见关于 Schönhage 算法和次二次整数 gcd 计算。
于 2009-09-27T11:54:36.270 回答
7
如果您在除法/余数比班次贵得多的机器上运行，请考虑二进制 GCD。
于 2009-09-27T13:31:48.463 回答