Calculadora de números primos

n es primo <=> d(n) = 2; previousPrime(97) = 97; nextPrime(97) = 97; nextPrime(1000000) = 1000003

n

El número entero que se comprueba: de 2 a 1000000. El límite inferior es deliberado y no heredado, porque el primo anterior de 1 no existe y una página que aceptara el 1 tendría una fila que no podría rellenar con honestidad. Si el 1 es primo es una pregunta de definición, y se responde en las preguntas de abajo y no en la calculadora

d(n)

El número de divisores positivos, que es la primera fila del resultado y la única evidencia sobre la que se apoya el veredicto. d(n) = 2 significa que lo dividen exactamente dos números, que es la definición de primo. El recuento viene de la rutina compartida de teoría de números, así que es el mismo valor que informan para la misma entrada la página de factores y la de descomposición en factores primos

d(n) = 2

La prueba en sí, escrita como una ecuación. Es una equivalencia y no una aproximación: un número es primo si y solo si tiene exactamente dos divisores. Para 97 los divisores son 1 y 97, así que el recuento es 2 y la insignia dice primo. Para 100 son 1, 2, 4, 5, 10, 20, 25, 50 y 100, así que el recuento es 9 y la insignia dice compuesto

previousPrime(n)

El mayor primo que es menor o igual que n. Es inclusivo por arriba, así que cuando n es primo la respuesta es el propio n. Para 100 la respuesta es 97; para 25 es 23; para 97 es 97. El intervalo es cerrado porque la alternativa necesitaría una regla sobre qué imprimir cuando n ya es primo, y una fila en blanco en un panel de resultados se lee como un fallo y no como un hecho

nextPrime(n)

El menor primo que es mayor o igual que n, con la misma regla inclusiva por abajo. Para 25 es 29, para 100 es 101 y para 97 es 97. Este sí puede salirse del rango de la entrada: nextPrime(1000000) es 1000003, un primo mayor que cualquier número que la página acepta, y se informa como respuesta en lugar de tratarse como fuera de límites

1e6 to 1e6 + 100

El entorno del techo de entrada, y la razón de que ahí arriba haga falta otra prueba. Los primos cercanos al millón son 999983 y 1000003, así que la búsqueda desde 1000000 tiene que mirar más allá del millón en una dirección. La rutina que cuenta divisores rechaza los argumentos por encima del millón y lanzaría una excepción, así que la búsqueda de vecinos usa su propia prueba, que no tiene ese límite; y las dos tienen que coincidir allí donde se solapan, que es lo que comprueban las filas de primos de los ejemplos

Elegir un módulo es la razón más práctica para querer un primo cerca de un número que ya has decidido. El número de posiciones de una tabla hash suele tomarse primo, porque un módulo primo reparte las claves que comparten un factor en lugar de dejarlas chocar: una tabla de 1000 posiciones manda todos los múltiplos de 25 a las mismas pocas casillas, y una de 997 no. El mismo instinto se aplica en criptografía, donde las claves se construyen con primos grandes y separados entre sí. Comprobar si un número es primo también resuelve rápido preguntas de divisibilidad: si un número no tiene ningún divisor primo hasta su raíz cuadrada, no tiene ninguno, y la insignia responde a eso en un paso en lugar de por ensayo. Algunos pasatiempos van simplemente sobre la primalidad: los primos gemelos, las distancias entre primos consecutivos y si un número dado es el producto de dos primos. Cuando la pregunta resulta ser sobre los factores mismos, la página de descomposición en factores primos rompe el número en primos y es la parada natural siguiente; cuando es sobre qué números dividen al tuyo, la página de factores los lista todos; y cuando el número probado no es primo y quieres saber de qué está hecho, el número de divisores de esta página es la primera pista y no la respuesta completa.

1. Un primo: 97

   1. Probamos los divisores de 97: el 2 no lo divide, y el 3, el 5, el 7 y el 11 tampoco
   2. Paramos en la raíz cuadrada: 10 × 10 = 100 ya supera 97, así que no queda nada por probar
   3. Los únicos divisores son 1 y 97, así que el recuento es 2 y el número es primo
   4. El primo anterior es el propio 97, porque 97 ya es primo y la búsqueda es inclusiva
   5. El primo siguiente también es 97, por la misma razón

   La entrada por defecto, y la ilustración más limpia de la regla inclusiva. Los dos vecinos vuelven como el propio número, lo que al principio parece que las filas no hicieron nada. Sí lo hicieron: el mayor primo que no supera 97 es 97, y el menor primo que no baja de 97 también es 97. La alternativa, una desigualdad estricta, dejaría esas dos filas sin nada que imprimir justo en las entradas en las que la página está más segura, y una fila vacía en un panel de resultados se lee como un error. Este caso es también donde se encuentran las dos pruebas independientes de la página: el número de divisores dice 2 y la búsqueda de vecinos confirma que 97 es primo, y llegan ahí con código distinto.

2. Un número compuesto: 100

   1. 100 es par, así que el 2 lo divide; termina en 00, así que el 4, el 5, el 10, el 20, el 25 y el 50 también
   2. Los divisores son 1, 2, 4, 5, 10, 20, 25, 50 y 100, nueve en total
   3. Nueve es más de dos, así que la insignia dice compuesto y no primo
   4. El mayor primo que no supera 100 es 97; el menor que no baja de 100 es 101
   5. Los dos vecinos quedan a un paso del número, que es el aspecto que tiene ser compuesto en medio de un hueco

   El caso que muestra a los vecinos haciendo trabajo de verdad. Cuando el número es compuesto, las dos filas de vecinos son la salida útil, porque responden a la pregunta que el lector tiene a continuación: si no es este número, ¿cuál? Noventa y siete y ciento uno son los primos más cercanos, y 100 se queda entre ellos. El recuento de nueve también merece un vistazo: es impar, lo que ocurre exactamente cuando el número es un cuadrado perfecto, y 100 es 10 al cuadrado. Así que un solo vistazo al recuento ya dice algo sobre la forma del número, antes de descomponerlo.

3. Un número justo por encima de un primo: 25

   1. Los divisores de 25 son 1, 5 y 25, tres, porque el 5 se empareja consigo mismo
   2. Tres es más de dos, así que 25 es compuesto
   3. Bajamos desde 25: 24, 23; el 23 es primo, así que es el primo anterior
   4. Subimos desde 25: 26, 27, 28, 29; el 29 es primo, así que es el primo siguiente
   5. El hueco aquí es de seis en total: 23 y 29 flanquean 25

   Un cuadrado perfecto, y esa es la razón de que el número de divisores sea impar; además es un caso en el que los dos vecinos están a distancias visiblemente distintas, dos por debajo y cuatro por arriba. El recuento de tres muestra también por qué el umbral correcto es dos y no un recuento de factores primos: 25 tiene un solo factor primo, el 5, pero no es primo, y el número de divisores lo detecta sin necesidad de mirar la descomposición.

La entrada debe ser un número entero de 2 a 1000000. El cero y el uno se rechazan, y el uno se rechaza por un motivo distinto del cero: es una cuestión de definición y no un número fuera de rango, y el primo anterior de 1 no existe. Los negativos se rechazan, porque la primalidad es una propiedad de los enteros mayores que 1 y, aunque en algunas ramas de las matemáticas exista una convención para primos negativos, esta página no adopta ninguna. Los decimales se rechazan en lugar de redondearse. El techo de un millón se aplica solo a la entrada: las dos filas de vecinos pueden informar legítimamente de un primo fuera de él, y el primo siguiente a un millón es 1000003, que se informa en lugar de rechazarse. La prueba que hay detrás del veredicto son divisiones sucesivas hasta la raíz cuadrada, instantáneas a este tamaño y desesperadas con un número de veinte cifras, y esa frontera es una propiedad del problema y no de esta implementación. La página informa de tres números y una insignia: no lista los divisores, no descompone un número compuesto y prueba un número cada vez en lugar de un intervalo. Las tablas de abajo son filas fijas y no una respuesta a tu entrada. Por último, un primo se informa como su propio primo anterior y siguiente, que es una elección deliberada de intervalo cerrado y no dos filas que no encontraron nada.

¿Es 1 un número primo?

No, y tampoco es un número compuesto. Un primo se define como un entero mayor que 1 con exactamente dos divisores positivos, y el 1 tiene un solo divisor, así que no cumple la definición por ninguno de los dos lados. Es una elección deliberada y no un descuido: si el 1 contara como primo, dejaría de ser cierto que todo número tiene exactamente una descomposición en factores primos, porque podrías multiplicar cualquier descomposición por 1 tantas veces como quisieras. Excluir el 1 es lo que mantiene limpio ese teorema. Y como es una cuestión de definición y no de aritmética, la página no acepta el 1 como entrada: la respuesta vive aquí.

¿Por qué el primo anterior y el siguiente vuelven como el propio número?

Porque las dos búsquedas son inclusivas. El primo anterior es el mayor primo que no supera tu número, y el primo siguiente es el menor primo que no baja de él. Cuando el número ya es primo, cumple las dos descripciones, así que las dos filas lo informan. La alternativa sería una desigualdad estricta, y entonces una entrada prima dejaría dos filas sin nada que imprimir. Una fila en blanco en un panel de resultados se lee como que algo ha ido mal, y la página no podría responder justo en el caso en el que está más segura. La misma convención aparece en el redondeo, donde un número que ya está en la precisión pedida vuelve sin cambios.

¿Por qué el primo siguiente puede ser mayor que un millón si la entrada no puede?

Porque el techo es un límite sobre lo que puedes preguntar, no sobre lo que puede ser la respuesta. El primo siguiente a 1000000 es 1000003, y negarse a imprimirlo sería negarse a responder a una pregunta perfectamente bien planteada sobre una entrada que la página aceptó. Así que la búsqueda de vecinos corre con su propia prueba, sin tope superior, mientras que el número de divisores sigue usando la rutina compartida, que solo cubre el rango. Eso implica que dos piezas de lógica deciden si un número es primo, una acotada y otra no, y se exige que coincidan allí donde se solapan, que es lo que comprueba el ejemplo del 97: el recuento dice 2 y la búsqueda de vecinos dice que 97 es primo.

¿Para qué se usa de verdad un número primo?

Sobre todo para dimensionar cosas. A las tablas hash se les suele dar un número primo de posiciones, porque un módulo primo reparte las claves que comparten un factor: una tabla con 1000 posiciones manda todos los múltiplos de 25 a las mismas pocas casillas, y una con 997 no. El mismo razonamiento vale para cualquier contador que da la vuelta: una longitud de ciclo prima evita resonar con patrones regulares de los datos. La criptografía es el otro uso grande, con claves construidas a partir de primos muy grandes y muy separados entre sí, y la seguridad se apoya en lo difícil que es volver a descomponer su producto en los dos primos de los que salió. Los usos pequeños están por todas partes: comprobar una afirmación de divisibilidad, ver si un número es el producto de dos primos y los pasatiempos clásicos sobre primos gemelos y sobre las distancias entre primos consecutivos.

¿Cómo decide la página, y con cuánta seguridad?

Contando divisores, que es exacto y no probabilístico. Un número es primo si y solo si tiene exactamente dos divisores positivos, así que el recuento zanja la cuestión sin posibilidad de respuesta equivocada y sin necesidad de fiarse de una prueba que pueda ser engañada. El recuento se hace por división por tentativa hasta la raíz cuadrada, y esa es la razón de que el techo sea un millón: más allá el método se vuelve lento, no poco fiable. Para números mucho mayores los métodos exactos son genuinamente impracticables y se usan pruebas probabilísticas, pero a este tamaño no hay motivo para aceptar nada menos que la certeza, y la página no lo hace.

¿Por qué se muestra el número de divisores y no solo el veredicto?

Porque el recuento es la razón del veredicto, y mostrarlo hace que los dos no puedan discrepar nunca: la insignia no es un segundo cálculo sino una lectura del número impreso a su lado. Además es útil por sí mismo. Un recuento impar significa que el número es un cuadrado perfecto, ya que la raíz cuadrada se empareja consigo misma y no con otro divisor. Un recuento de 2 es la definición de primo. Un recuento grande para el tamaño del número dice que tiene muchos factores pequeños, que es la clase de número que acumula divisores deprisa. Y conecta esta página con las otras: la de descomposición en factores primos informa del mismo número de divisores para la misma entrada, calculándolo a partir de los exponentes, así que las dos páginas se comprueban entre sí.

• Números primos: actividades en Smartick — identificación de primos, factorización de números compuestos y reglas de divisibilidad con primos, que es la división por tentativa que aplica esta página — Smartick (España)
• Prime Number — the definition, the divisor-count test, and why 1 is excluded by it — Wolfram MathWorld (United States)
• Prime Gaps — the distances between consecutive primes, and what the neighbourhood of a million looks like — Wolfram MathWorld (United States)
• Composite Number — the complement of the primes, and why 1 belongs to neither group — Wolfram MathWorld (United States)