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

Nombres premiers tronquables

Lister les nombres premiers, jusqu'à une limite, qui restent premiers quand on retire des chiffres à l'une ou l'autre extrémité.

Ce que vous allez apprendre

  • Retirer des chiffres à l'une ou l'autre extrémité d'un nombre
  • Tester chaque troncature
  • Rassembler les résultats dans l'ordre

Problème

Prenez 3797. En retirant des chiffres par la gauche, on obtient 797, 97 et 7 ; en les retirant par la droite, 379, 37 et 3. Tous ces nombres sont premiers, tout comme 3797. On dit qu'un tel nombre premier est tronquable des deux côtés. Les nombres premiers à un chiffre n'ont rien à retirer et ne comptent pas. Listez tous les nombres premiers tronquables des deux côtés de 10 à limit.

Implémentez truncatable_primes(limit).

Entrée

limit : le plus grand nombre à examiner.

Sortie

Renvoyez ces nombres premiers dans l'ordre croissant, ou une liste vide s'il n'y en a aucun.

Contraintes

1 ≤ limit ≤ 100 000

Exemples

Exemple 1
Entrée :
limit = 40

Sortie attendue :
expected = [23, 37]
Entrée :
long long limit = 40;

Sortie attendue :
std::vector<long long> expected = {23, 37};
Entrée :
long limit = 40;

Sortie attendue :
long[] expected = new long[] {23, 37};

Explication

23 (2, 3) et 37 (3, 7) conviennent ; 13 échoue car 1 n'est pas premier, et 29 échoue car 9 ne l'est pas. [23, 37].

Exemple 2
Entrée :
limit = 10

Sortie attendue :
expected = []
Entrée :
long long limit = 10;

Sortie attendue :
std::vector<long long> expected = {};
Entrée :
long limit = 10;

Sortie attendue :
long[] expected = new long[] {};

Explication

Sous 10, il n'y a que des nombres premiers à un chiffre, et ils ne comptent pas : [].

Comment l'aborder

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

Indice 1

Retirer un chiffre à droite revient à diviser par 10.

Indice 2

Retirer des chiffres à gauche revient à prendre le reste modulo une puissance de 10.

Indice 3

Toutes les troncatures jusqu'à un seul chiffre doivent être premières, ainsi que le nombre lui-même.

Complexité attendue

temps O(limit × d × √limit), espace supplémentaire O(answer), proportionnel à la taille de la réponse

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.