Problem
Primzahlzwillinge sind zwei Primzahlen, die sich um 2 unterscheiden, etwa 11 und 13 oder 17 und 19. Finde alle solchen Paare, deren größere Zahl höchstens limit ist.
Implementiere twin_primes(limit).
Bei großen Grenzen solltest du alle Primzahlen auf einmal mit einem Sieb bestimmen, statt jede Zahl einzeln zu testen.
Eingabe
limit: Der größte Wert, den die größere Primzahl eines Paares haben darf.
Ausgabe
Gib eine Liste von Paaren [p, p + 2] zurück, bei denen beide Zahlen Primzahlen sind und p + 2 ≤ limit gilt, aufsteigend nach p sortiert. Gibt es keine Paare, gibst du eine leere Liste zurück.
Einschränkungen
0 ≤ limit ≤ 10^6
Beispiele
Eingabe:
limit = 20
Erwartete Ausgabe:
expected = [
[3, 5],
[5, 7],
[11, 13],
[17, 19]
]
Eingabe:
long long limit = 20;
Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {
{3, 5},
{5, 7},
{11, 13},
{17, 19}
};
Eingabe:
long limit = 20;
Erwartete Ausgabe:
long[][] expected = new long[][] {
new long[] {3, 5},
new long[] {5, 7},
new long[] {11, 13},
new long[] {17, 19}
};
Erläuterung
Die Primzahlen bis 20 sind 2, 3, 5, 7, 11, 13, 17, 19; diejenigen mit Abstand 2 ergeben [[3, 5], [5, 7], [11, 13], [17, 19]].
Eingabe:
limit = 6
Erwartete Ausgabe:
expected = [
[3, 5]
]
Eingabe:
long long limit = 6;
Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {
{3, 5}
};
Eingabe:
long limit = 6;
Erwartete Ausgabe:
long[][] expected = new long[][] {
new long[] {3, 5}
};
Erläuterung
3 und 5 sind beide prim und 5 ≤ 6, aber 7 liegt über der Grenze, also nur [[3, 5]].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Ein Sieb findet alle Primzahlen bis 10^6 viel schneller, als jede Zahl einzeln zu testen.
Hinweis 2
Prüfe danach jedes p mit p + 2 ≤ limit.
Hinweis 3
Das erste Paar ist (3, 5), jede Grenze unter 5 ergibt also eine leere Liste.
Erwartete Komplexität
Zeit O(limit log log limit), zusätzlicher Speicher O(limit)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.