Descomposición en factores primos y test de primalidad
Introduzca un número entero para saber si es primo, obtener su descomposición en factores primos, y la lista de sus divisores. Un número primo solo tiene dos divisores : 1 y él mismo — su descomposición contiene entonces un único factor, elevado a la potencia 1.
Calculadora
Resultados
| — ¿es primo? | — |
| Descomposición en factores primos | — |
| Cantidad de divisores positivos | — |
| Suma de los divisores | — |
| Lista de divisores | — |
Cómo se calcula una descomposición en factores primos
División por ensayo entre 2, 3, 5, 7… hasta √n: cada divisor hallado es un factor primo
Cantidad de divisores = producto de los (exponente + 1) de cada factor primo
Basta con probar los divisores hasta la raíz cuadrada de n : si ningún factor primo menor o igual que √n divide a n, entonces n es primo — cualquier divisor mayor tendría un «complemento» más pequeño ya probado. La cantidad total de divisores se deduce directamente de los exponentes de la descomposición, sin necesidad de enumerarlos todos.
Un asterisco junto a un término remite a su entrada del glosario de cierre.
Definición de número primo y de número compuesto
Un entero mayor que 1 es primo* cuando solo admite dos divisores positivos: 1 y él mismo. No hay manera de escribirlo como producto de dos enteros más pequeños.
2, 3, 5, 7, 11, 13, 17, 19, 23: esa es la cabeza de la lista, la que se memoriza en 1º de ESO. 4 no está (2 × 2), ni 9 (3 × 3), ni 15 (3 × 5). Esos son compuestos*. A partir del 2 no hay un tercer cajón: o es primo, o se descompone.
En esta página la respuesta se lee en la descomposición. ¿Un solo factor, elevado a 1? Es primo. Dos factores, o un exponente mayor que 1, y es compuesto. 9 = 3² no es primo: un único primo en pantalla no basta si la potencia delata el producto 3 × 3. 360, el valor de ejemplo, sale 2³ × 3² × 5: compuesto, con veinticuatro divisores positivos.
El 1 queda fuera: unicidad de la factorización
La duda reaparece cada septiembre. El 1 solo es divisible entre 1, ¿entonces?
La definición pide dos divisores distintos. El 1 tiene uno. Tampoco es compuesto: no se parte en enteros más chicos. Queda aparte. El motivo de fondo es el teorema fundamental de la aritmética*: todo entero > 1 se escribe de una sola manera como producto de primos, salvo el orden. Si el 1 fuera primo, se podrían pegar tantos unos como se quisiera (1 × 1 × 5 = 5) y se caería la unicidad. Por eso se deja fuera. No es un capricho del libro de texto.
El formulario no acepta nada por debajo de 2. El 1, sencillamente, no tiene nada que factorizar. En cambio, el 2 sí: es el primer primo, y el único par, cosa que se retoma más abajo.
La criba de Eratóstenes: listar primos hasta un tope
Para un solo n basta la división por ensayo hasta √n. Si lo que se busca es todos los primos hasta un tope N, cambia la herramienta: la criba de Eratóstenes*.
- Se escriben los enteros del 2 al N.
- El 2 es primo: se tachan todos sus múltiplos (4, 6, 8…).
- El primero que no está tachado, el 3, es primo: se tachan 6, 9, 12…
- Se sigue con 5, 7 y así hasta √N. Lo que quede sin tachar es primo.
No es un test suelto. Es un barrido. Cada compuesto se visita unas pocas veces. Para llenar una tabla hasta unos millones no hay nada más simple de programar. Esta página no criba el intervalo: responde a un n. Generar los cincuenta millones de primos por debajo de mil millones porque se ha escrito 360 no tiene sentido.
En 1º de ESO la criba se hace hasta 100, a veces hasta 200, en una cuadrícula. Ahí se ve de un golpe que los pares (salvo el 2) desaparecen a la primera pasada, y que los múltiplos de 5 se llevan los que acaban en 0 o en 5. Los criterios de divisibilidad son, al cabo, esa misma idea leída cifra a cifra.
División por ensayo hasta la raíz: el test de esta página
¿Por qué basta llegar a √n? Porque los divisores van por parejas. Si n = a × b y a ≤ b, entonces a ≤ √n. Un factor mayor que la raíz tendría un «complemento» más pequeño, ya comprobado. Si ninguno de esos candidatos divide a n, n es primo.
probar 2, 3, 5, 7… hasta √n; si ninguno divide, n es primo
Hasta mil millones, √n ronda los 31.623. Un bucle corto. La página responde al momento y, de paso, construye la descomposición: cada vez que un p divide, se cuenta el exponente y se sigue con el cociente.
Por cierto, no hace falta probar todos los enteros hasta la raíz. Tras el 2 solo se ensayan impares, o mejor aún, solo primos. El programa de esta página recorre enteros; para mil millones sigue siendo instantáneo. A otra escala, la diferencia se nota, y entonces ya no se factoriza: se lanza un test de primalidad, apartado más abajo.
Para qué sirven los primos: claves, tablas y códigos
En clase se factorizan. En una máquina esconden información.
La criptografía de clave pública —el nombre que circula es RSA*— se apoya en un producto n = p × q de dos primos enormes. Multiplicar p y q es inmediato. Recuperar p y q a partir de n, sin conocerlos, queda fuera de alcance en cuanto esos primos tienen unos cientos de cifras. Esa es la clave pública: n puede mostrarse; los factores, no.
También aparecen como tamaño de tablas hash (un módulo primo reparte mejor las colisiones), en algunos generadores seudoaleatorios, en códigos correctores. Siempre la misma idea: módulo un primo, la aritmética se porta; el producto de dos primos grandes se resiste a desmontarse. No obstante, nada de eso se parece a factorizar 360 en un examen.
Los primos de esta página no tienen nada que ver con los de una clave. El tope es mil millones: diez cifras, un ejercicio de instituto. Un módulo RSA habitual tiene 2.048 bits, más de 600 cifras. Factorizar 360 no enseña a romper una clave.
Gemelos, Mersenne y los récords
Algunos primos llegan de dos en dos, a distancia 2: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31)… Son los primos gemelos. Se conocen pares enormes. Sigue sin saberse si hay infinitos.
Los números de Mersenne tienen la forma 2p − 1. Para que esa expresión sea prima, p tiene que serlo: necesario, no suficiente. 211 − 1 = 2.047 = 23 × 89, y 11 es primo. ¿Por qué importan? Porque casi todos los récords de «primo más grande conocido» son de Mersenne: la forma admite un test propio (Lucas–Lehmer) que deja atrás la división por ensayo. GIMPS, una red de máquinas voluntarias, persigue esos récords desde los años noventa.
Esta calculadora no llega ahí. 219 − 1 = 524.287 aún cabe bajo mil millones; 231 − 1 = 2.147.483.647 ya no. Gemelos y Mersenne se pinchan con el formulario como cualquier otro entero. No son un modo aparte.
Números perfectos y la suma de divisores
Un número es perfecto cuando la suma de sus divisores propios —todos menos él mismo— lo vuelve a formar.
6 = 1 + 2 + 3. 28 = 1 + 2 + 4 + 7 + 14. Luego 496 y 8.128. La lista se ralea enseguida. Todo perfecto par se escribe 2p−1(2p − 1) en cuanto 2p − 1 es un primo de Mersenne (teorema de Euclides–Euler). Nadie ha visto un perfecto impar. Nadie ha demostrado que no existan. Las dos preguntas —impares, infinitud de los pares— siguen abiertas, lo cual no impide que 6 y 28 circulen en todos los manuales de ESO.
La tabla de esta página suma todos los divisores, n incluido. Un perfecto aparece entonces con suma 2n. Para 28, la celda marca 56. De ahí el atajo: si la suma duplica al número, es perfecto; si se queda corta, es deficiente; si se pasa, abundante. 12, por ejemplo, es abundante (1 + 2 + 3 + 4 + 6 + 12 = 28).
Factorizar para hallar el MCD y simplificar fracciones
Simplificar una fracción es quitar lo que numerador y denominador tienen en común. Esos factores comunes son el MCD.
Si a = 2³ × 3² × 5 y b = 2² × 3 × 7, el MCD toma el mínimo de cada exponente: 2² × 3 = 12. El mcm toma el máximo: 2³ × 3² × 5 × 7 = 2.520. 360/12 sobre 84/12 da la fracción irreducible 30/7. No hace falta Euclides si las dos descomposiciones ya están, siempre que los números sigan siendo lo bastante pequeños para obtenerlas.
La calculadora de MCD y mcm trabaja al revés, con el algoritmo de Euclides, también para una lista. Las dos páginas se contestan. Romper un entero y comparar varios es el mismo material, dos gestos. Por lo demás, factorizar un trinomio ax² + bx + c es otra familia: ahí el discriminante y las raíces entran en la ecuación de segundo grado, no en esta descomposición.
De la lista de 1º de ESO a la infinitud de Bachillerato
En 1º de ESO se pide la lista hasta 30 o hasta 50, la criba hasta 100 y la descomposición de un número de tres cifras. El 1 se discute cinco minutos y se aparca. En 2º y 3º, el mismo material sirve para el MCD, el mcm y las fracciones. Nada más.
En Bachillerato de ciencias el acento se desplaza: hay infinitos primos, la densidad baja, aparecen conjeturas (Goldbach, gemelos) y, de refilón, RSA. Nadie pide factorizar a mano un número de diez cifras. Lo que se pide es no confundir un teorema con una conjetura, y no tratar el 1 como primo «porque es más simple».
Al respecto, esta página cubre el piso de ESO con un techo de mil millones: bastante para un identificador, un DNI, un código postal extendido o un problema de olimpiada; demasiado poco para hacer creer que se ataca una clave.
El 2 es el único primo par, y hay infinitos primos
Todo par distinto de 2 es divisible entre 2, luego compuesto. El 2 se queda solo. Suena a obviedad de patio, y acorta muchos argumentos. Pasado el 2, solo se buscan impares. La criba empieza tachando una casilla de cada dos: la paridad es el primer filtro, el más tosco. Los gemelos, por su lado, son casi siempre dos impares a distancia 2. El par (2, 3) es consecutivo, no gemelo. Un entero que termina en 0, 2, 4, 6 u 8 y no es 2 no es primo.
Euclides muestra que hay infinitos sin dar una fórmula para el siguiente. Si solo hubiera una cantidad finita p1, p2, …, pk, el número N = p1 × p2 × … × pk + 1 no sería divisible entre ninguno de ellos (siempre resta 1). O N es primo —y faltaba en la lista— o tiene un factor primo nuevo. En ambos casos la lista estaba incompleta. Se puede repetir indefinidamente.
N = (producto de los primos supuestos) + 1 → primo nuevo, o factor nuevo
No se dice cómo hallar el próximo. Solo que siempre queda uno. La densidad baja: entre 1 y 100 hay 25 primos; entre 1 y 1.000, 168. Más raros no significa últimos. En realidad es de las demostraciones más cortas del instituto, y de las que más se recuerdan.
La conjetura de Goldbach y el tope de mil millones
Todo entero par estrictamente mayor que 2 sería suma de dos primos. 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 = 5 + 5, y así. Se ha comprobado por ordenador hasta cotas enormes. No se ha demostrado. Es una conjetura, no un teorema. Una versión más débil (todo impar ≥ 7 es suma de tres primos) sí está demostrada. La forma fuerte, la que se cuenta en Bachillerato, sigue abierta.
Esta página no comprueba Goldbach. Factoriza un entero. Tomar un par, romperlo y buscar a mano dos primos que lo recompongan es un pasatiempo; no certifica la conjetura.
¿Por qué el tope está en mil millones? Porque la división por ensayo sigue siendo instantánea y la lista de divisores cabe en pantalla —salvo en unos pocos muy compuestos, cuya lista se oculta (más de 300 divisores). Más allá, el cálculo no «se rompe» enseguida en una máquina actual. El interés didáctico sí. A la postre, un entero de doce cifras ya no se comprueba a mano, y las necesidades de verdad —claves, récords— viven en escalas donde este método no pinta nada. √n se queda en unos 31.000, un bucle que la página termina antes de pintarse. Un entero más grande ya no es esta herramienta. Ni el mismo problema.
Glosario
- Número primo
- Entero mayor que 1 cuyos únicos divisores positivos son 1 y él mismo. Los primeros: 2, 3, 5, 7, 11…
- Número compuesto
- Entero mayor que 1 que no es primo: se escribe como producto de enteros más pequeños. 4, 9, 15, 360 lo son.
- Teorema fundamental de la aritmética
- Todo entero mayor que 1 se descompone de una sola manera como producto de primos, salvo el orden de los factores. Es la razón de que el 1 no se considere primo.
- Criba de Eratóstenes
- Método para listar todos los primos hasta un tope N: se tachan los múltiplos de cada primo hallado, hasta √N. Lo que queda sin tachar es primo.
- RSA
- Criptosistema de clave pública que cifra con el producto n = p × q de dos primos enormes. Multiplicar es fácil; factorizar n, no. Los primos de esta página (hasta mil millones) no sirven para una clave real.