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 at 22:59.

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 at 06:54.

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 at 01:15.

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
- Join large list of pairs
- 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

- What does the (?) mean when using ls utility?
- Found published work that doesn't reference previous related work
- Did China ever consider a phonetic writing system?
- How do you keep track of X-per-day abilities?
- Integers sorted by their digital roots
- How can I deal with the blame-game played by my colleague in office?
- VIC-II transistor count
- Why does Gerard say “I don’t care!” to Kimble in the tunnel?
- How to Reduce Repeated If/Else Logic in Code
- How to write a story without conflict, like "My Neighbour Totoro"?
- How to deal with unknown genders in English?
- Is it appropriate to ask a software developer about extra hours spent for side projects and open-source (as a hobby)?
- "Integral Milking:" Does anyone else do this?
- What is the word for using one word to replace another for cosmetic reasons?
- What is on/in my lens?
- Is it really mandatory to practise sight reading at the piano?
- Listing methods to prove that two groups are not isomorphic
- Proving trigonometric problem from given trigonometric equations
- Did more gay men die in NYC during the AIDS crisis than US soldiers in Vietnam?
- Could you actually make Sandy's Treedome in real life?
- Why might plasma weapons have different colors, even when made by the same manufacturer?
- Being alive today: the most improbable coïncidence?
- Why can a bill be blocked by one MP saying the word "object"?
- Simple question about probability