Problème
Faire tourner un nombre consiste à déplacer son premier chiffre à la fin : 197 devient 971, puis 719. Un nombre premier est circulaire si toutes ses rotations sont elles aussi premières ; 197 est donc circulaire. Comptez les nombres premiers circulaires de 2 à limit. Une rotation peut dépasser la limite ; elle doit quand même être première.
Implémentez circular_primes(limit).
Entrée
limit : le plus grand nombre à examiner.
Sortie
Renvoyez le nombre de nombres premiers p ≤ limit qui sont circulaires.
Contraintes
1 ≤ limit ≤ 100 000
Exemples
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 est premier) et 17 (71 est premier) sont circulaires, mais pas 19 (91 = 7 × 13) : 7.
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
Il n'y a aucun nombre premier jusqu'à 1, donc la réponse est 0.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Une rotation déplace le premier chiffre à la fin ; un nombre à d chiffres a d rotations.
Indice 2
Convertir le nombre en chaîne facilite les rotations.
Indice 3
Les rotations peuvent dépasser la limite, donc testez directement leur primalité.
Complexité attendue
temps O(limit × d × √(10^d)) avec divisions successives, espace supplémentaire O(d)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.