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