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
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].
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.