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