Einfach 0 gelöst 0% Erfolgsquote

Primzahlzwillinge

Liste alle Primzahlzwillinge (p, p + 2) bis zu einer Grenze auf.

Das lernst du

  • Die Primzahlen bis zu einer Grenze mit einem Sieb markieren
  • Nach Primzahlen mit Abstand 2 suchen
  • Grenzen behandeln, die zu klein für ein Paar sind

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

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

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

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.