Algorithm for checking if a list of integers is pairwise coprime

user2782067 06/12/2018. 3 answers, 710 views
algorithms primes

Are thre any efficient algorithms for checking if a list of integers is pairwise coprime, or would a more general algorithm be the best option available?

3 Answers

Draconis 06/12/2018.

First, two facts about coprime integers:

  • Iff $a$ and $b$ are coprime, then $ab = \mathrm{lcm}(a,b)$
  • Iff $a$ is coprime to both $b$ and $c$, then $a$ is coprime to $bc$

It follows from this that a set of distinct integers $\{a, b, \cdots z\}$ is pairwise coprime if its product is equal to its least common multiple.

You can compute the least common multiple by using the following identity:

$$\mathrm{lcm}(a,b,c) = \mathrm{lcm}(a,\mathrm{lcm}(b,c))$$

Assuming you have $n$ numbers with $k$ digits each, and multiplying/dividing/modding two numbers is $O(1)$ (which may or may not be a good assumption depending on your model), then:

  • Calculating the product of your set takes $O(n)$
  • Calculating the gcd of two numbers takes $O(k)$
  • Calculating the lcm of two numbers thus also takes $O(k)$, by reduction to gcd
  • So calculating the lcm of your entire set takes $O(nk)$

Thus, the time complexity of the entire algorithm is $O(nk)$.

D.W. 06/13/2018.

Yes. The naive approach of checking each pair of numbers takes quadratic time, but there are more efficient algorithms. There is a nearly-linear time algorithm, described in the following paper:

Daniel J. Bernstein. Factoring into coprimes in essentially linear time. Journal of Algorithms 54 (2005), 1--30.

See also That's almost as efficient as you could possibly hope for.

To clarify how this helps with your situation, once you've found a coprime basis and factored each element over the basis, it is trivial to check whether they are pairwise coprime: if they are not pairwise coprime, then some pair will have a common factor, and that will be a factor that is in the coprime basis and that is present in the factorization of both. If there is no factor that is common to present in the factorization of two or more numbers, then you know the numbers are pairwise coprime. Once you have the factorizations, it is easy to check in linear time whether any numbers in more than one factorization.

MackTuesday 06/13/2018.

Find the prime factors of each number. The numbers are all pairwise coprime if and only if every prime in the entire collection is distinct. This check can be done in O(n) time using a hash table.

Edit: Draconis' answer is better though, because it doesn't require any factorization. GCD computation is faster if your numbers are big and/or prime.

Related questions

Hot questions


Popular Tags