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?

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

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.

- Type-checking algorithms
- What is most efficient for GCD?
- FFT-less $O(n\log n)$ algorithm for pairwise sums
- Counting the number of N-dimensional coprime integer vectors
- Finding coprimes closest to a certain target
- What sorting algorithm should be used for this array?
- Algorithm to check the distance between integers
- Algorithm for generating coprime number sequences?
- Algorithm for finding maximum mutually coprime subset of a multiset of integers
- System of congruences with non-pairwise coprime moduli

- In mathematics, is there such a conjecture, the problem was proved to be solvable, but the direct solution is not yet known?
- What to do if you are above timberline and your descent is cut off by a large forest fire?
- Understanding a Cyclic Group Proof
- Was an elderly woman forcibly euthanized in the Netherlands?
- Compelled Duel with Sanctuary Spell Interaction
- Written warning for allegedly "slacking off" (in Germany)
- If an airline goes bust or insolvent, what happens to frequent flyer miles and reward tickets?
- Were myopic slaves more valuable in ancient Greece?
- Does multiplying the likelihood by a constant change the Bayesian inference using MCMC?
- Ubuntu /etc/hosts addresses in the form *.*.*.*
- Should I count the hours that I wait for my code to run?
- What's the significance of the nickel crystal in the Davisson and Germer experiment?
- How to talk about my comfortable lifestyle without sounding like I'm bragging?
- Ordinary writing or Prose: how to make it immersive?
- Why would the Doctor get his tie?
- Ask a girl whether she would like to come back to a hotel with me on a night out without being creepy
- Just another riley riddle
- Concatenate multiple lines into "special-character"-delimited string
- Extending a class by parameter in Python
- How to deal with "Scrooge McDucks" in my fixed-currency-amount game?
- Using rage faces in presentation
- How was C ported to architectures that had no hardware stack?
- Does Wild Shape count as a spell?
- Why don't people hand pump their tires?