Mittel 0 gelöst 0% Erfolgsquote

Goldbach-Zerlegung

Schreibe eine gerade Zahl als Summe zweier Primzahlen, wobei die erste Primzahl so klein wie möglich ist.

Das lernst du

  • Einen Primzahltest per Probedivision schreiben, der bei √n aufhört
  • Kandidaten in aufsteigender Reihenfolge durchsuchen und beim ersten Treffer aufhören
  • Ein Paar in der geforderten Reihenfolge zurückgeben

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

Beispiel 1
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].

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.