Tous les défis
Moyen 0 résolus 0 % de réussite

Circular Primes

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

Ce que vous allez apprendre

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

Problème

Afficher la traduction

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.

Contraintes

1 ≤ limit ≤ 100,000

Exemples

Exemple 1
Entrée :
limit = 20

Sortie attendue :
expected = 7
Entrée :
long long limit = 20;

Sortie attendue :
long long expected = 7;
Entrée :
long limit = 20;

Sortie attendue :
long expected = 7;

Explication

2, 3, 5, 7, 11, 13 (31 is prime) and 17 (71 is prime) are circular, but 19 is not (91 = 7 × 13): 7.

Exemple 2
Entrée :
limit = 1

Sortie attendue :
expected = 0
Entrée :
long long limit = 1;

Sortie attendue :
long long expected = 0;
Entrée :
long limit = 1;

Sortie attendue :
long expected = 0;

Explication

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

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

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

Indice 2

Turning the number into a string makes rotation easy.

Indice 3

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

Complexité attendue

O(limit × d × √(10^d)) time with trial division, O(d) extra space

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.