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

Nombres premiers circulaires

Compter les nombres premiers, jusqu'à une limite, dont toutes les rotations des chiffres sont aussi premières.

Ce que vous allez apprendre

  • Faire tourner les chiffres d'un nombre
  • Vérifier une condition sur chaque rotation
  • Compter les nombres qui la satisfont

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

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 est premier) et 17 (71 est premier) sont circulaires, mais pas 19 (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

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.

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.