Mittel 0 gelöst 0% Erfolgsquote

Kreisprimzahlen

Zähle die Primzahlen bis zu einer Grenze, bei denen jede Rotation der Ziffern ebenfalls prim ist.

Das lernst du

  • Die Ziffern einer Zahl rotieren
  • Eine Bedingung für jede Rotation prüfen
  • Die Zahlen zählen, die alle Prüfungen bestehen

Problem

Beim Rotieren einer Zahl wandert ihre erste Ziffer ans Ende: Aus 197 wird 971, dann 719. Eine Primzahl heißt Kreisprimzahl, wenn auch jede ihrer Rotationen prim ist, 197 ist also eine Kreisprimzahl. Zähle die Kreisprimzahlen von 2 bis limit. Eine Rotation darf größer als die Grenze sein, prim sein muss sie trotzdem.

Implementiere circular_primes(limit).

Eingabe

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

Ausgabe

Gib zurück, wie viele Primzahlen p ≤ limit Kreisprimzahlen sind.

Einschränkungen

1 ≤ limit ≤ 100.000

Beispiele

Beispiel 1
Eingabe:
limit = 20

Erwartete Ausgabe:
expected = 7
Eingabe:
long long limit = 20;

Erwartete Ausgabe:
long long expected = 7;
Eingabe:
long limit = 20;

Erwartete Ausgabe:
long expected = 7;

Erläuterung

2, 3, 5, 7, 11, 13 (31 ist prim) und 17 (71 ist prim) sind Kreisprimzahlen, 19 aber nicht (91 = 7 × 13): 7.

Beispiel 2
Eingabe:
limit = 1

Erwartete Ausgabe:
expected = 0
Eingabe:
long long limit = 1;

Erwartete Ausgabe:
long long expected = 0;
Eingabe:
long limit = 1;

Erwartete Ausgabe:
long expected = 0;

Erläuterung

Bis 1 gibt es keine Primzahlen, also lautet die Antwort 0.

So gehst du vor

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

Hinweis 1

Eine Rotation schiebt die erste Ziffer ans Ende. Eine d-stellige Zahl hat d Rotationen.

Hinweis 2

Wandelst du die Zahl in einen String um, ist das Rotieren ganz einfach.

Hinweis 3

Rotationen können größer als die Grenze sein, teste sie also direkt auf Primzahl.

Erwartete Komplexität

Zeit O(limit × d × √(10^d)) mit Probedivision, zusätzlicher Speicher O(d)

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.