Comprobador de números primos

Cómo usar el comprobador de números primos

1. Escribe un Número entero. También se aceptan expresiones: 2^61-1, 10^12+39, 20!+1 o 3711.
2. La respuesta aparece mientras escribes; pulsa Comprobar para dar más tiempo a la factorización de un número difícil.
3. Lee el veredicto, la Descomposición en factores primos, el Número de divisores, el Primo anterior y el Primo siguiente. El panel Por qué explica cómo se ha llegado a la respuesta, y Copiar factorización copia el producto de primos.
4. Para listar primos, rellena Desde y Hasta en Números primos en un intervalo y pulsa Listar primos.

Se aceptan números de hasta 2048 bits (unas 617 cifras), y todo se calcula en tu navegador.

Qué hace que un número sea primo

Un número primo es un número entero mayor que 1 cuyos únicos divisores son 1 y él mismo: 2, 3, 5, 7, 11, 13… Un número con otros divisores es compuesto, y se puede escribir de una única forma como producto de primos: su descomposición en factores primos (360 = 2³ × 3² × 5). Los números 0 y 1 no son ni primos ni compuestos, y 2 es el único primo par.

El número de divisores se deduce de la factorización: suma 1 a cada exponente y multiplica. 360 = 2³ × 3² × 5 tiene (3 + 1)(2 + 1)(1 + 1) = 24 divisores. Un primo siempre tiene exactamente 2.

Cómo funciona el test

• Los números pequeños (menores de un millón) se comprueban por división de prueba: si ningún primo hasta la raíz cuadrada divide al número, es primo. No hace falta seguir, porque un número compuesto siempre tiene un factor no mayor que su raíz cuadrada.
• Los números más grandes se dividen primero entre todos los primos menores que 1000 y después pasan el test de Miller–Rabin. Con las 13 bases 2, 3, 5, …, 41, está demostrado que este test es exacto para todos los números menores que 3,3 × 10²⁴, lo que incluye todos los enteros de 64 bits. Para esos números la respuesta es segura.
• Por encima de 3,3 × 10²⁴ se usan 25 bases, y un número que las supera todas se indica como primo probable. La probabilidad de error es inferior a 1 entre 10¹⁵, pero no es una demostración matemática. Cuando el test falla, el número es compuesto con total seguridad.

Cómo se factorizan los números

Los factores pequeños se encuentran por división de prueba. Las partes compuestas más grandes se descomponen con el algoritmo rho de Pollard (variante de Brent), que encuentra factores de hasta unas 10 cifras en una fracción de segundo. Los números más difíciles, como el producto de dos primos de 15 cifras o más, pueden tardar mucho más que cualquier límite de tiempo, así que la factorización se detiene al cabo de unos segundos. El último factor se marca entonces como compuesto no descompuesto, y al pulsar Comprobar de nuevo se le da más tiempo.

Primos en un intervalo

La lista por intervalos usa una criba de Eratóstenes segmentada, que tacha los múltiplos de cada primo. Admite hasta 1.000.000 de números por intervalo con un límite superior de hasta 10¹². El recuento abarca todo el intervalo y se enumeran los primeros 2000 primos. Por ejemplo, hay 25 primos entre 1 y 100 y 78.498 por debajo de un millón.