Laz*_*zer 9 algorithm number-theory greatest-common-divisor
一种方法是计算他们的gcd并检查它是否为1.
有更快的方法吗？
jas*_*son 12
欧几里得算法(计算gcd)非常快.当从中随机均匀地绘制两个数时[1, n],计算它们的平均步数gcd是O(log n).每个步骤所需的平均计算时间是数字的二次方.
有些替代方案表现得稍好一些(即每个步骤的位数都是数字的次级),但它们仅对非常大的整数有效.例如,参见OnSchönhage的算法和子二次整数gcd计算.