我一直在看这里的问题和其他地方关于 gcd 算法(euclid 和扩展、lehmer、二进制和扩展)的文章,但我需要一些稍微不同的东西:我需要从列表中确定两个或多个数字的相对素数.
除了为我正在测试的集合中的每对元素运行一个或多个上述算法(蛮力版本)之外,是否有更有效的算法来检查任何(或所有)所选元素是否互质? (具体来说,在这种情况下,我需要的“互质”定义是包容性的:对于元素 a、b 和 c,如果任何元素与任何其他元素互质,则它们的集合对于我的目的是“互质”——它们并不都是需要与所有其他元素互质,因此一旦找到互质关系,测试就可以结束)。
(备用标题:“三个或更多数字的最大公分母/约数”)
我尝试了上面提到的暴力版本。它工作“很好”,但我需要非常快速地进行多次迭代才能使程序发挥最佳功能,因此我正在尽可能提高效率,而且似乎很少提及针对此特定问题的替代解决方案,我认为 stackoverflow 可能值得一试。
供参考,目前的伪代码是:
boolean coprime = false
brute: for each unit (somewhere between dozens and thousands)
brute1: for each element e1 (somewhere between two and 16)
for each other element e2
if gcd(e1, e2) ==1
coprime = true
break brute
OR
//using the identity gcd(a, b, c) = gcd(a, gcd(b, c)):
if
brute2: gcd(list.get(0), brute2(list.copy.remove(0)) etc.
从某种意义上说,恕我直言,brute1 和 brute2 之间的决定是 brute1 有时很快但有时很慢,而 brute2 具有一致的速度并且可能总体上更好,因为一些聪明的 return 语句可以帮助克服不得不退出整个一旦找到一个互质关系,就堆叠起来。然而,理想的是一种算法,它一次测试多个元素或以某种方式过滤以增加更快地找到互素的概率(我意识到可能不存在)。
编辑:虽然我给出了直接在对之间或递归运行 gcd 算法的示例,但这实际上不是我的问题。我的问题是,有没有人听说过一种算法,或者任何真正的方法,可以同时找到两个以上元素的 gcd 而无需单独对(无论是直接还是递归)?