Tutte le sfide
Media 0 risolte 0% di accettazione

Primi troncabili

Elenca i primi fino a un limite che restano primi togliendo cifre da una qualsiasi delle due estremità.

Cosa imparerai

  • Togliere cifre da una delle due estremità di un numero
  • Verificare ogni troncamento
  • Raccogliere i risultati in ordine

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

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

Esempio 2
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.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.