Nombres simples P53208


Statement
 

pdf   zip

En aquest problema direm que un nombre és simple si la seva factorització no conté més de dos factors primers diferents. Per exemple, 1, 8=238 = 2^3, 20=22⋅520 = 2^2 \cdot 5 i 23 són nombres simples, mentre que 126=2⋅32⋅7126 = 2 \cdot 3^2 \cdot 7 i 420=22⋅3⋅5⋅7420 = 2^2 \cdot 3 \cdot 5 \cdot 7 no ho són.

Donats diversos naturals, podeu decidir eficientment si són simples?

Entrada

L’entrada consisteix en diverses nn, totes entre 1 i 10910^9.

Sortida

Per a cada nn, digueu si és simple o no.

Observacions

Els jocs de proves privats grossos contenen molts nombres costosos de decidir. La solució esperada fa una mena de garbell d’Eratòstenes (diguem, d’un milió de nombres) abans de començar a llegir l’entrada, i diverses optimitzacions.

En funció de l’eficiència de la vostra solució, el jutge us donarà una estimació (sobre 100) de la nota màxima que podreu obtenir.

Public test cases

  • Input

    1
8
20
23
126
420

    Output

    SI
SI
SI
SI
NO
NO

  • Input

    1000000000
999999997
999999991
999999988
999999984
999999996
999999986
999999937

    Output

    SI
NO
SI
NO
NO
NO
SI
SI
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++