CODEWITHSUNDEEP
arraysalgorithm
Jytug
Jytug

Reputation: 1116

Finding whether there are two coprime numbers in an array

I'm trying to find an algorithm that for a given array A = [a1, a2, ..., a_n] of integers returns true if there are two indexes i !== j such that gcd(ai, aj) = 1 (and false otherwise). I'm trying to minimalize the complexity of this algorithm.

Of course, the obvious solution would be to use Euclid's algorithm for each pair (ai, aj), but its pesimistic complexity is n(n+1)/2 times the complexity of Euclid's algorithm.

Is there a way to do that in O(n) or O(n*log(n))?

Upvotes: 1

Views: 2949

Answers (2)

Raj Mittal
Raj Mittal

Reputation: 1

For existence of atleast two number that are coprime the GCD of whole array must be 1.

Upvotes: 0

Antti Huima
Antti Huima

Reputation: 25542

Let hasCoprimePair(S) be procedure that returns True if there is a pair of coprimes S and otherwise False, and let it have a two argument variant hasCoprimePair(S, T) that returns True if there exists a pair coprimes, one integer in S and one in T, and otherwise False.

Now let p be a prime number. Take a set S (of integers) and divide it into two sets, T and U, so that T contains those elements of S that are divisible by p and U contains the other elements (those not divisible by p). Because every element in T is divisible by p, it follows that hasCoprimePair(T) = False necessarily. So we have

hasCoprimePair(S) = hasCoprimePair(T, U) or hasCoprimePair(U)

The first subproblem (hasCoprimePair(T, U)) can be solved in |T|x|U| GCD-operations and the second subproblem is recursive; you can again split it using a different value of p this time. Splitting S into T and U sets requires O(n) time, so you save some GCD-operations compared to the naive algorithm but the asymptotic complexity is still quadratic.

Upvotes: 2

Related Questions