Mittel 0 gelöst 0% Erfolgsquote

Circular Primes

Count the primes up to a limit whose every digit rotation is also prime.

Das lernst du

  • Rotate the digits of a number
  • Check a condition on every rotation
  • Count numbers that pass

Problem

Übersetzung anzeigen

Rotating a number moves its first digit to the end: 197 becomes 971, then 719. A prime is circular when every rotation is prime too, so 197 is circular. Count the circular primes from 2 to limit. A rotation may be larger than the limit; it still has to be prime.

Implement circular_primes(limit).

Input

limit: The largest number to check.

Output

Return how many primes p ≤ limit are circular.

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 is prime) and 17 (71 is prime) are circular, but 19 is not (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

There are no primes up to 1, so the answer is 0.

So gehst du vor

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

Hinweis 1

Rotating once moves the first digit to the end; a d-digit number has d rotations.

Hinweis 2

Turning the number into a string makes rotation easy.

Hinweis 3

Rotations can be bigger than the limit, so test them for primality directly.

Erwartete Komplexität

O(limit × d × √(10^d)) time with trial division, O(d) 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.