Problema
Prendi 3797. Togliendo cifre da sinistra ottieni 797, 97 e 7; togliendole da destra ottieni 379, 37 e 3. Sono tutti primi, e lo è anche 3797. Un primo di questo tipo si dice troncabile da entrambi i lati. I primi di una sola cifra non hanno nulla da togliere e non contano. Elenca tutti i primi troncabili da entrambi i lati da 10 a limit.
Implementa truncatable_primes(limit).
Input
limit: il numero più grande da controllare.
Output
Restituisci i primi in ordine crescente. Se non ce ne sono, restituisci una lista vuota.
Vincoli
1 ≤ limit ≤ 100 000
Esempi
Input:
limit = 40
Output atteso:
expected = [23, 37]
Input:
long long limit = 40;
Output atteso:
std::vector<long long> expected = {23, 37};
Input:
long limit = 40;
Output atteso:
long[] expected = new long[] {23, 37};
Spiegazione
23 (2, 3) e 37 (3, 7) vanno bene; 13 no perché 1 non è primo, e 29 no perché 9 non è primo. [23, 37].
Input:
limit = 10
Output atteso:
expected = []
Input:
long long limit = 10;
Output atteso:
std::vector<long long> expected = {};
Input:
long limit = 10;
Output atteso:
long[] expected = new long[] {};
Spiegazione
Sotto 10 ci sono solo primi di una cifra, che non contano: [].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Togliere una cifra da destra equivale a dividere per 10.
Suggerimento 2
Togliere cifre da sinistra equivale a prendere il resto modulo una potenza di 10.
Suggerimento 3
Ogni troncamento, fino alla singola cifra, deve essere primo, e così anche il numero stesso.
Complessità attesa
tempo O(limit × d × √limit), spazio aggiuntivo O(answer), cioè proporzionale alla risposta
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.