8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Just to make sure, you mean that every pair of integers in your set is coprime? $\endgroup$ – Draconis Jun 12 '18 at 22:42
  • 2
    $\begingroup$ yes, every combination of 2 integers must be coprime $\endgroup$ – user2782067 Jun 12 '18 at 22:47
8
$\begingroup$

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)$.

$\endgroup$
  • 2
    $\begingroup$ If OP is actually implementing this it may be worthwhile to evaluate whether the product/lcm are equal for each number as they are read rather than after multiplying all of them/lcm-ing all of them. This won't change the complexity but if you expect most lists to not be coprime (as would be the case for a long list of random numbers) then it will most likely be faster $\endgroup$ – sudo rm -rf slash Jun 13 '18 at 2:28
  • 5
    $\begingroup$ @D.W. I believe the point is that by testing incrementally, you can bail early once the first non-coprime example is found, as opposed to only after processing the whole list. Since we expect most lists to not be pairwise coprime and we don't have any information about the list being tested, we should expect that the list will probably not be pairwise coprime, and therefore proceed with a procedure that is optimized for that common case. $\endgroup$ – Andrea Reina Jun 13 '18 at 7:25
  • $\begingroup$ @AndreaReina exactly thanks for writing it more clearly $\endgroup$ – sudo rm -rf slash Jun 13 '18 at 11:02
  • $\begingroup$ Another implementation note... Using gcd==1 instead of lcm==prod is probably easier since as far as I know the best lcm algos use the gcd anyway $\endgroup$ – sudo rm -rf slash Jun 13 '18 at 13:37
  • 1
    $\begingroup$ If you count the number of digits of the numbers, it doesn't make sense to assume that multiplication and division are $O(1)$. They're $\Omega(k^a)$ for some $k \gt 1$. $\endgroup$ – Gilles Jun 13 '18 at 21:54
4
$\begingroup$

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 https://cstheory.stackexchange.com/q/3393/5038. 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.

$\endgroup$
  • 2
    $\begingroup$ I don't see how Factoring over a coprime base relates to checking if a list of integers is pairwise coprime (yet). $\endgroup$ – greybeard Jun 13 '18 at 5:34
  • $\begingroup$ @greybeard, see edited answer -- I added a paragraph at the end explaining. $\endgroup$ – D.W. Jun 13 '18 at 6:54
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Factoring is very slow. As far as we know, there's no efficient algorithm for factoring -- and we certainly don't know of one that takes O(n) time. Basically, this algorithm will be close to exponential time (technically, subexponential but superpolynomial time). $\endgroup$ – D.W. Jun 13 '18 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.