Si hay un tipo de números importante y que es base de las matemáticas ese es el de los números primos.
Se dice que un número es primo cuando sólo es divisible por él mismo y la unidad*. Es decir, cuando no puede descomponerse en producto de otros números.
Estos números han interesado a los matemáticos desde el inicio de los tiempos, habiendo pruebas de que se conocía su existencia antes del año 1000 a.C. En la antigua Grecia se crearon las primeras tablas de números primos.
Cuando Gauss era joven, recibió como regalo un libro que contenía una lista de números primos. Pero algo en la lista los hacía desconcertantes: no había una manera de, dado un número primo, encontrar el siguiente de la serie. Parecía que habían sido elegidos al azar, así que se decidió a buscar un modelo que pudieran cumplir. En un mundo sin ordenadores, donde las cuentas se tenían que hacer de forma manual, era evidente la ventaja de encontrar ese modelo. Cuando Gauss llegó a la conclusión de que no podía encontrar la respuesta que buscaba, pensó en cambiar la pregunta… y su nueva cuestión fue:
Una vez que se planteó esto, llegó a realizar una aproximación que aún hoy, con las herramientas que tenemos, sigue considerándose buena. Esta aproximación dice que el número de primos entre 1 y N es de \(\frac{N}{ln(N)}\), donde ln() es el logaritmo natural.
Esto se concreta en el Teorema de los Números Primos, que dice lo siguiente:
\[ \frac{\pi(n) }{n}\to\frac{1}{ln(n)} \quad \text{para n suficientemente grandes} \]donde \(\pi(n)\) representa el número de primos entre 1 y n, y el "\(\to\)" significa "tiende a". De esta manera consideraremos el error producido por esta aproximación como:
\[ error=\frac{\pi(n)}{n}-\frac{1}{ln(n)} \]El programa recibirá una serie de casos de prueba.
Cada caso de prueba se especificará en una línea con dos enteros positivos. El primero, n, será un número natural positivo, menor que 100.000, para el que se quiere poner a prueba la aproximación de Gauss. El segundo, m será un valor entre 0 y 5 que servirá para calcular el máximo error permitido mediante la fórmula:
\[ error = \frac{1}{10^m} \quad \text{siendo $m$ un entero} \]El caso de prueba 0 0 será especial y marcará el final de la entrada.
El programa indicará Mayor si el error (en valor absoluto) de la aproximación de Gauss es mayor que el máximo permitido, Igual si es el mismo, y Menor si es menor.
10 3 750 2 65535 2 65535 3 10000 2 99999 1 0 0
Mayor Mayor Menor Mayor Mayor Menor