Números invictos P65824


Statement
 

pdf   zip

thehtml

A estas alturas ya deberías saber qué es un número primo (incluso mi primo lo sabe…) pero, ¿conoces los números invictos? ¡Seguro que no! Decimos que un número es invicto cuando, al borrar los dígitos que no son primos, nos queda un número que sí lo es. ¡Qué obsesión los matemáticos y los primos!

En este problema te pedimos que nos digas cuantos números invictos hay de 1 a n.

Entrada

Una secuencia de valores n, cada uno de ellos en una línea.

Salida

Para cada entrada n debes decir cuántos números invictos podemos encontrar en el intervalo [1, n]. Tu programa dispone de 1 segundo de CPU para resolver cada entrada.

Puntuación

  • Test1:  ‍40 Puntos ‍

    Resolver varias entradas con no más de 10 valores n entre 1 y 1000.

  • Test2:  ‍20 Puntos ‍

    Resolver varias entradas con no más de 30000 valores n entre 1 y 1000.

  • Test3:  ‍30 Puntos ‍

    Resolver varias entradas con no más de 10 valores n entre 1 y 106.

  • Test4:  ‍10 Puntos ‍

    Resolver varias entradas con no más de 30000 valores n entre 1 y 106.

Public test cases
  • Input

    1
    9
    99
    999
    

    Output

    0
    4
    52
    519
    
  • Information
    Author
    Enric S. Cusell
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++