Problem
Die Goldbachsche Vermutung besagt, dass jede gerade Zahl größer als 2 die Summe zweier Primzahlen ist. Bewiesen ist sie bis heute nicht, aber sie wurde weit über die hier vorkommenden Zahlen hinaus überprüft. Oft gibt es mehrere Möglichkeiten: 28 = 5 + 23 = 11 + 17. Gesucht ist die Zerlegung, deren kleinere Primzahl so klein wie möglich ist.
Implementiere goldbach_partition(n).
Wenn du p = 2, 3, 5, ... durchprobierst und jeweils testest, ob n − p prim ist, findest du die Antwort schnell, denn ein kleines p funktioniert fast immer. Um eine Zahl bis 10^9 per Probedivision auf Primalität zu testen, brauchst du nur Teiler bis etwa 31.623.
Eingabe
n: Eine gerade Zahl größer als 2.
Ausgabe
Gib [p, q] zurück, wobei p und q Primzahlen sind, p + q = n und p ≤ q gilt und p die kleinste Primzahl ist, für die das funktioniert.
Einschränkungen
4 ≤ n ≤ 10^9, n ist gerade
Beispiele
Eingabe:
n = 28
Erwartete Ausgabe:
expected = [5, 23]
Eingabe:
long long n = 28;
Erwartete Ausgabe:
std::vector<long long> expected = {5, 23};
Eingabe:
long n = 28;
Erwartete Ausgabe:
long[] expected = new long[] {5, 23};
Erläuterung
28 − 2 = 26 und 28 − 3 = 25 sind nicht prim, aber 28 − 5 = 23 ist es, also lautet die Antwort [5, 23].
Eingabe:
n = 4
Erwartete Ausgabe:
expected = [2, 2]
Eingabe:
long long n = 4;
Erwartete Ausgabe:
std::vector<long long> expected = {2, 2};
Eingabe:
long n = 4;
Erwartete Ausgabe:
long[] expected = new long[] {2, 2};
Erläuterung
Die einzige Möglichkeit ist 2 + 2, also lautet die Antwort [2, 2].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Probiere p = 2, 3, 4, ... durch und hör beim ersten p auf, bei dem sowohl p als auch n − p prim sind.
Hinweis 2
Ein Primzahltest muss Teiler nur bis zur Quadratwurzel ausprobieren.
Hinweis 3
Da du beim kleinsten p aufhörst, gilt p ≤ n − p ganz automatisch.
Erwartete Komplexität
Zeit O(k √n), wobei k die Anzahl der probierten Kandidaten ist, zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.