Mittel 0 gelöst 0% Erfolgsquote

Goldbach Partition

Write an even number as the sum of two primes, using the smallest possible first prime.

Das lernst du

  • Write a trial-division prime test that stops at √n
  • Search candidates in increasing order and stop at the first hit
  • Return a pair in the required order

Problem

Übersetzung anzeigen

Goldbach's conjecture says that every even number greater than 2 is the sum of two primes. It has never been proven, but it has been checked far beyond the numbers here. Often there are several ways: 28 = 5 + 23 = 11 + 17. Find the one whose smaller prime is as small as possible.

Implement goldbach_partition(n).

Trying p = 2, 3, 5, ... and testing whether n − p is prime finds the answer quickly, because a small p almost always works. Testing a number up to 10^9 for primality by trial division only needs divisors up to about 31,623.

Input

n: An even number greater than 2.

Output

Return [p, q] where p and q are primes, p + q = n, p ≤ q, and p is the smallest prime for which this works.

Einschränkungen

4 ≤ n ≤ 10^9, n is even

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 and 28 − 3 = 25 are not prime, but 28 − 5 = 23 is, so the answer is [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

The only option is 2 + 2, so the answer is [2, 2].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Try p = 2, 3, 4, ... and stop at the first p where both p and n − p are prime.

Hinweis 2

A prime test only needs to try divisors up to the square root.

Hinweis 3

Since you stop at the smallest p, p ≤ n − p comes for free.

Erwartete Komplexität

O(k √n) time where k is the number of candidates tried, O(1) extra space

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.