Mittel 0 gelöst 0% Erfolgsquote

Truncatable Primes

List the primes up to a limit that stay prime as digits are removed from either end.

Das lernst du

  • Remove digits from either end of a number
  • Test every truncation
  • Collect results in order

Problem

Übersetzung anzeigen

Take 3797. Removing digits from the left gives 797, 97 and 7; removing them from the right gives 379, 37 and 3. All of them are prime, and so is 3797. Call such a prime two-sided truncatable. One-digit primes have nothing to remove and do not count. List every two-sided truncatable prime from 10 to limit.

Implement truncatable_primes(limit).

Input

limit: The largest number to check.

Output

Return the primes in increasing order. Return an empty list if there are none.

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), 37 (3, 7) both work; 13 fails because 1 is not prime and 29 fails because 9 is not. [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

Only one-digit primes are below 10 and they do not count: [].

So gehst du vor

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

Hinweis 1

Removing from the right is division by 10.

Hinweis 2

Removing from the left is taking the remainder modulo a power of 10.

Hinweis 3

Every truncation down to a single digit must be prime, and so must the number.

Erwartete Komplexität

O(limit × d × √limit) time, O(answer) 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.