Teiler-Partition

Gegeben seien rationale Zahlen a\_1,a\_2,\dots ,a_n mit \gcd(a\_1,a\_2,\dots ,a_n)=1. Ich möchte nun den größten Faktor $k$ finden, durch den die meisten dieser Zahlen teilbar sind. Für $n=1$ ist $k=a_1$ , für $n=2$ ist $k=1$ . Für höhere n fällt mir kein besserer Algorithmus ein, als alle Zahlen in ihre Primfaktoren zu zerlegen und dann zu schauen, ob ein Faktor in $n-1$ dieser Zerlegungen vorkommt (falls nicht, dann in $n-2$ etc.).

Zwei Beispiele:
$a\_1=10,a\_2=50,a\_3=8,a\_4=13,k=2$ (2 teilt drei der Zahlen, 5 und 10 nur zwei)
$a\_1=9,a\_2=15,a_3=25,k=5$ (3 und 5 teilen beide zwei Zahlen, aber 5 ist größer)

Kann man das Problem effizienter lösen als die Primfaktorzerlegung?

Was meinst du mit "die meisten"?

Bashar

Für rationale Zahlen sind die Begriffe Teilbarkeit und ggT trivial (von der Null abgesehen ist alles durch alles teilbar, alles ist ein ggT von allem) du meinst sicher natürliche Zahlen.

Dann hast du, wenn ich mich nicht irre, einen Fall von Mehrkriterienoptimierung: Du möchstest einen möglichst großen Faktor, der möglichst viele der Zahlen teilt. Wenn du bei einem Abstriche machst, kannst du beim anderen mehr erreichen. Wie löst du das auf?

Ja, meinte natürliche Zahlen.

"Möglichst viele Zahlen teilen" > "Möglichst groß". Das Möglichst-groß-Kriterium spielt nur eine Rolle, wenn mehrere Kandidaten gleich viele Zahlen teilen. Ich habe das Möglichst-groß-Kriterium ehrlich gesagt nur eingeführt, weil es eindeutig sein soll, wenn z.B. 6 die Lösung ist (2 und 3 wären ansonsten auch mögliche Lösungen).

Mit "die Zahl, die die meisten teilen kann" meine ich jene natürlich Zahl, die die höchste Anzahl der Zahlen a\_1,a\_2,\dots ,a_n teilen kann. Formal wären das die Hochpunkte dieser Funktion: f: \mathbb{N} \rightarrow \mathbb{N}\_0, x \mapsto \sum\_{i=0}^n [x|a_i] wobei [\;] die Prädikatabbildung ist. Wenn eine zusammengesetzte Zahl ein Hochpunkt ist, so sind auch ihre Primfaktoren jeweils Hochpunkte (mit einem kleineren x-Wert). Nur der Hochpunkt mit dem größten x-Wert ist von Interesse.

Bashar

Das ist dann doch immer k=1.

Columbo

Edit: .