Nombres simples P53208

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 = 2^3$, $20 = 2^2 \cdot 5$ i 23 són nombres simples, mentre que $126 = 2 \cdot 3^2 \cdot 7$ i $420 = 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 $n$, totes entre 1 i $10^9$.

Sortida

Per a cada $n$, 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.