Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Abschneidbare Primzahlen

Liste die Primzahlen bis zu einer Grenze auf, die prim bleiben, wenn man von links oder von rechts Ziffern abschneidet.

Das lernst du

  • Ziffern an beiden Enden einer Zahl entfernen
  • Jede abgeschnittene Zahl prüfen
  • Ergebnisse in der richtigen Reihenfolge sammeln

Problem

Nimm 3797. Schneidet man von links Ziffern ab, erhält man 797, 97 und 7, schneidet man von rechts ab, erhält man 379, 37 und 3. Alle diese Zahlen sind prim, und 3797 selbst auch. Eine solche Primzahl nennen wir beidseitig abschneidbar. Einstellige Primzahlen haben nichts zum Abschneiden und zählen nicht. Liste alle beidseitig abschneidbaren Primzahlen von 10 bis limit auf.

Implementiere truncatable_primes(limit).

Eingabe

limit: Die größte zu prüfende Zahl.

Ausgabe

Gib die Primzahlen in aufsteigender Reihenfolge zurück. Gibt es keine, gib eine leere Liste zurück.

Einschränkungen

1 ≤ limit ≤ 100.000

Beispiele

Beispiel 1
Eingabe:
limit = 40

Erwartete Ausgabe:
expected = [23, 37]
Eingabe:
long long limit = 40;

Erwartete Ausgabe:
std::vector<long long> expected = {23, 37};
Eingabe:
long limit = 40;

Erwartete Ausgabe:
long[] expected = new long[] {23, 37};

Erläuterung

23 (2, 3) und 37 (3, 7) funktionieren beide. 13 scheitert, weil 1 keine Primzahl ist, und 29, weil 9 keine ist. [23, 37].

Beispiel 2
Eingabe:
limit = 10

Erwartete Ausgabe:
expected = []
Eingabe:
long long limit = 10;

Erwartete Ausgabe:
std::vector<long long> expected = {};
Eingabe:
long limit = 10;

Erwartete Ausgabe:
long[] expected = new long[] {};

Erläuterung

Unter 10 gibt es nur einstellige Primzahlen, und die zählen nicht: [].

So gehst du vor

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

Hinweis 1

Rechts abschneiden heißt durch 10 teilen.

Hinweis 2

Links abschneiden heißt den Rest modulo einer Zehnerpotenz nehmen.

Hinweis 3

Jede abgeschnittene Zahl bis hinunter zu einer einzelnen Ziffer muss prim sein, und die Zahl selbst auch.

Erwartete Komplexität

Zeit O(limit × d × √limit), zusätzlicher Speicher O(answer)

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.