我试图找到一个算法，对于给定的数组a=[a1，a2，…，a_n]的整数，如果有两个索引I，则返回true！=j，使得gcd（ai，aj）=1（否则为false）。我试图最小化这种算法的复杂性。
当然，明显的解决方案是使用Euclid算法的每对（AI，AJ），但其悲观的复杂性是N（n + 1）/ 2倍的复杂性的Euclid算法。
在O（n）或O（n*log（n））中有这样做的方法吗？
最佳答案
让HasCoprimEpAIR（S）是一个过程，如果有一对Coprimes S和其他false，则返回true，并让它具有两个参数变体HasCoprimEpAIR（S，T），如果存在对Coprimes、S中的一个整数和T中的一个整数，否则返回true。
现在让p成为质数。取一个整数集S，把它分成两个集T和U，这样T就包含了S中那些可以被p整除的元素，U就包含了其它元素（那些不能被p整除的元素）因为T中的每个元素都可以被p整除，所以hasCoprimePair（T）=False是必然的所以我们有
hasCoprimePair(S) = hasCoprimePair(T, U) or hasCoprimePair(U)
第一个子问题（hasCoprimePair（T，U））可以在| T | x | U | GCD操作中求解，第二个子问题是递归的；这次可以使用不同的p值再次拆分它分裂成T和U集需要O（n）的时间，所以你保存一些GCD操作相比，朴素算法，但渐近复杂性仍然是二次。