Algorithm for checking if a list of integers is pairwise coprime

user2782067 06/12/2018. 3 answers, 715 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 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.


HighResolutionMusic.com - Download Hi-Res Songs

1 BLACKPINK

Kiss And Make Up flac

BLACKPINK. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
2 Martin Garrix

Waiting For Tomorrow flac

Martin Garrix. 2018. Writer: Pierce Fulton;Mike Shinoda;Martijn Garritsen;Brad Delson.
3 John Legend

Written In The Stars flac

John Legend. 2018. Writer: Kiana Brown;Santoy;Kevin White;Mike Woods;MZMC;The Heavy Group;Rice N' Peas.
4 Martin Garrix

Access flac

Martin Garrix. 2018. Writer: Martin Garrix.
5 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
6 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
7 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
8 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
9 Post Malone

Sunflower flac

Post Malone. 2018. Writer: Louis Bell;Billy Walsh;Carter Lang;Swae Lee;Post Malone.
10 Dyro

Latency flac

Dyro. 2018. Writer: Martin Garrix;Dyro.
11 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
12 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.
13 Zara Larsson

Ruin My Life flac

Zara Larsson. 2018. Writer: Delacey;Michael Pollack;Stefan Johnson;Jordan Johnson;Sermstyle;Jackson Foote.
14 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
15 ZAYN

Fingers flac

ZAYN. 2018. Writer: Zayn Malik;Alex Oriet;David Phelan.
16 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
17 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
18 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
19 Blinders

Breach (Walk Alone) flac

Blinders. 2018. Writer: Dewain Whitmore;Ilsey Juber;Blinders;Martin Garrix.
20 Julia Michaels

There's No Way flac

Julia Michaels. 2018. Writer: Ian Kirkpatrick;Justin Tranter;Julia Michaels;Lauv.

Related questions

Hot questions

Language

Popular Tags