Fermat vs. Pitagoras 

De fondo

La computadora generó y ayudó en la prueba y verificación ocupando un pequeño empleo en el reino de las Ciencias de la computación. La primera prueba del problema de los cuatro colores fue completado con la ayuda de un programa de computadora y esfuerzos corrientes en verificación han tenido éxito en verificar la traducción de código de alto nivel a nivel del chip.

Este problema trata de computar cifras relacionadas a parte del último teorema de Fermat: que no existe soluciones enteras de tex2html_wrap_inline29 para n > 2.

El problema

Dado un entero positivo N, escribe un programa que calcule dos cantidades respecto la solución de

displaymath22

donde x, y, y z son valores enteros positivos menores o iguales N. Tienes que computar el número de triples (x,y,z) tal que x<y<z y ellos son primos relativos, es decir no tienen un común divisor mayor que 1.También tienes que calcular el número de valorestex2html_wrap_inline51 tal que p no es parte de algún triple.

La entrada

La entrada consiste de una secuencia de enteros positivos, uno por línea. Cada entero en el archivo de entrada es menor o igual a 1,000,000. La entrada termina con fin de archivo.

La salida

Para cada entero N en el archivo de entrada imprime dos enteros separados por un espacio. El primer entero es el número de primos relativos triples (tal que cada componente de el triple es tex2html_wrap_inline57 ). El segundo número es el número de enteros positivos tex2html_wrap_inline57 que no son parte que no son parte de algun triple cuyos componentes son todos tex2html_wrap_inline57 . Debe haber una línea de salida por cada línea de entrada.

Ejemplo de entrada

10
25
100

Ejemplo de salida

1 4
4 9
16 27