Algorithmus zum Überprüfen, ob eine Liste von Ganzzahlen paarweise koprime ist

Gibt es effiziente Algorithmen zur Überprüfung, ob eine Liste von Ganzzahlen paarweise koprime ist, oder wäre ein allgemeinerer Algorithmus die beste verfügbare Option?

algorithms primes user2782067
quelle

Nur um sicherzugehen, meinst du, dass jedes Paar von ganzen Zahlen in deinem Set Koprime ist?

Draconis

Ja, jede Kombination von 2 ganzen Zahlen muss

Coprime

Antworten:

Zunächst zwei Fakten zu Coprime-Ganzzahlen:

Wenn und Koprime sind, dann ist $a$ $b$ $ab = \mathrm{lcm}(a,b)$
Iff coprime sowohl ist und , dann ist coprime zu $a$ $b$ $c$ $a$ $bc$

Daraus folgt, dass eine Menge unterschiedlicher Ganzzahlen paarweise Koprime ist, wenn ihr Produkt gleich dem kleinsten gemeinsamen Vielfachen ist. $\{a, b, \cdots z\}$

Sie können das am wenigsten verbreitete Vielfache mithilfe der folgenden Identität berechnen:

l c m (a, b, c) = l c m (a, l c m (b, c))

$\mathrm{lcm}(a,b,c) = \mathrm{lcm}(a,\mathrm{lcm}(b,c))$

Angenommen, Sie haben Zahlen mit jeweils Ziffern und das Multiplizieren / Teilen / Modifizieren von zwei Zahlen ist (was je nach Modell eine gute Annahme sein kann oder nicht), dann: $n$ $k$ $O(1)$

Für die Berechnung des Produkts Ihres Satzes wird $O(n)$
Die Berechnung des gcd zweier Zahlen erfordert $O(k)$
Die Berechnung des lcm zweier Zahlen ergibt somit auch durch Reduktion auf gcd $O(k)$
Die Berechnung des lcm Ihres gesamten Satzes erfordert also $O(nk)$

Somit ist die zeitliche Komplexität des gesamten Algorithmus . $O(nk)$

Draconis
quelle

Wenn OP dies tatsächlich implementiert, kann es sinnvoll sein, zu bewerten, ob das Produkt / lcm für jede gelesene Zahl gleich ist, anstatt sie alle zu multiplizieren / lcm zu multiplizieren. Dies wird die Komplexität nicht ändern, aber wenn Sie erwarten, dass die meisten Listen nicht koprime sind (wie es bei einer langen Liste von Zufallszahlen der Fall wäre), wird es höchstwahrscheinlich schneller sein

sudo rm -rf Schrägstrich

@DW Ich glaube, der Punkt ist, dass Sie durch inkrementelles Testen frühzeitig auf Kaution gehen können, sobald das erste Nicht-Coprime-Beispiel gefunden wurde, anstatt erst nach der Verarbeitung der gesamten Liste. Da wir davon ausgehen, dass die meisten Listen nicht paarweise koprime sind und wir keine Informationen über die getestete Liste haben, sollten wir erwarten, dass die Liste wahrscheinlich nicht paarweise koprime ist, und daher mit einem Verfahren fortfahren, das für diesen häufigen Fall optimiert ist .

Andrea Reina

@AndreaReina genau danke für das klarere Schreiben

sudo rm -rf Schrägstrich

Noch ein Implementierungshinweis ... Die Verwendung von gcd == 1 anstelle von lcm == prod ist wahrscheinlich einfacher, da meines Wissens die besten lcm-Algen die gcd sowieso verwenden

sudo rm -rf slash

Wenn Sie die Anzahl der Ziffern der Zahlen zählen, ist es nicht sinnvoll anzunehmen, dass Multiplikation und Division

. Sie sind

für einige

O (1)

$O(1)$

Ω (k^{a})

$\Omega(k^a)$

k > 1

$k \gt 1$

Gilles 'SO - hör auf böse zu sein'

Ja. Der naive Ansatz, jedes Zahlenpaar zu überprüfen, benötigt quadratische Zeit, aber es gibt effizientere Algorithmen. Es gibt einen nahezu linearen Zeitalgorithmus, der im folgenden Artikel beschrieben wird:

Daniel J. Bernstein. Berücksichtigung von Koprimes in im Wesentlichen linearer Zeit . Journal of Algorithms 54 (2005), 1–30.

Siehe auch https://cstheory.stackexchange.com/q/3393/5038 . Das ist fast so effizient, wie Sie es sich nur wünschen können.

Um zu verdeutlichen, wie dies in Ihrer Situation hilft, ist es trivial zu überprüfen, ob es sich um eine paarweise Koprime handelt, wenn Sie eine Koprime-Basis gefunden und jedes Element über die Basis hinweg berücksichtigt haben. Wenn es sich nicht um eine paarweise Koprime handelt, hat ein Paar ein gemeinsames Paar Faktor, und das wird ein Faktor sein, der in der Coprime-Basis liegt und der in der Faktorisierung von beiden vorhanden ist. Wenn bei der Faktorisierung von zwei oder mehr Zahlen kein gemeinsamer Faktor vorhanden ist, wissen Sie, dass die Zahlen paarweise koprime sind. Sobald Sie die Faktorisierungen haben, können Sie in der linearen Zeit leicht überprüfen, ob Zahlen in mehr als einer Faktorisierung vorhanden sind.

DW
quelle

Ich sehe (noch) nicht, wie es sich Factoring over a coprime basebezieht checking if a list of integers is pairwise coprime.

Graubart

@greybeard, siehe bearbeitete Antwort - Ich habe am Ende einen Absatz hinzugefügt, der erklärt.

Finden Sie die Primfaktoren jeder Zahl. Die Zahlen sind alle paarweise koprime, wenn und nur wenn jede Primzahl in der gesamten Sammlung unterschiedlich ist. Diese Überprüfung kann in O (n) -Zeit mithilfe einer Hash-Tabelle durchgeführt werden.

Bearbeiten: Die Antwort von Draconis ist jedoch besser, da keine Faktorisierung erforderlich ist. Die GCD-Berechnung ist schneller, wenn Ihre Zahlen groß und / oder prim sind.

MackDienstag
quelle

Factoring ist sehr langsam. Soweit wir wissen, gibt es keinen effizienten Algorithmus für das Factoring - und wir kennen sicherlich keinen, der O (n) Zeit benötigt. Grundsätzlich liegt dieser Algorithmus nahe an der Exponentialzeit (technisch gesehen subexponentielle, aber superpolynomielle Zeit).