Algorithm for checking if a list of integers is pairwise coprime

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?

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

StackExchange Computer Science Q#93030, answer score: 9