Factorización en números primos
Descompón un número entero en sus factores primos, lista sus divisores y comprueba si es primo.
Se ejecuta enteramente en tu navegador. No se sube, registra ni guarda nada.
Factorización en primos
2^3 × 3^2 × 5
- ¿Es primo?
- no
- Factores primos distintos
- 3
- Cuántos divisores
- 24
- Divisores
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
Todo número entero mayor que 1 es un producto de primos, y solo hay un producto así para él: ese es el teorema fundamental de la aritmética. Esto lo encuentra, y con él todo lo que se deriva: cuántos divisores tiene el número y cuáles son.
Cómo funciona
División por tanteo, con un atajo: una vez sacados el 2 y el 3, todos los primos restantes están a un lado o al otro de un múltiplo de seis, así que los candidatos avanzan de seis en seis en lugar de de dos en dos. Lo que sobreviva a la criba es primo y entra como último factor.
Los divisores se construyen a partir de la factorización y no probando todos los números hasta n. Un número escrito como 2³ × 3² × 5 tiene (3+1) × (2+1) × (1+1) = 24 divisores, y cada uno es una elección de cuántos de cada primo tomar, así que listarlos no cuesta nada una vez conocida la factorización.
El techo es un billón. La división por tanteo llega como mucho hasta la raíz cuadrada del número, que ahí son un millón de pasos: rápido. Por encima, un número que resultara ser el producto de dos primos grandes dejaría la página cargando durante un minuto, así que se niega.
Ejemplos
| Caso | Entrada | Resultado |
|---|---|---|
| Un número con muchos divisores | 360 | 2³ × 3² × 5: 24 divisores |
| Un primo | 97 | 97: primo, 2 divisores |
| Una potencia de dos | 1024 | 2¹⁰: 11 divisores |
Preguntas frecuentes
¿Por qué empieza en 2 y no en 1?
Porque el 1 no tiene factorización en primos, y llamarlo primo rompería la unicidad sobre la que se apoya toda la materia: si el 1 fuera primo, el 6 sería 2 × 3, y 1 × 2 × 3, y 1 × 1 × 2 × 3, y ya no habría una sola respuesta. El cero es todavía peor: todos los números lo dividen.
¿Cuántos divisores tiene un número?
Suma uno a cada exponente de la factorización y multiplica. 360 es 2³ × 3² × 5, así que 4 × 3 × 2 = 24. Un primo tiene 2 —él mismo y el 1— y un cuadrado perfecto tiene siempre un número impar de ellos, porque uno de los divisores es su propia pareja.
¿Por qué hay un techo?
La división por tanteo es exacta y rápida hasta que deja de serlo. El peor caso es un producto de dos primos cercanos a la raíz cuadrada, y el límite de aquí está donde ese caso todavía devuelve dentro de una carga de página. Un rechazo te dice qué ha pasado; un tiempo agotado no te dice nada.
¿Así es como se rompen las claves de cifrado?
No, y ahí está la gracia. RSA se apoya en la dificultad de factorizar un número de unos cientos de cifras; la división por tanteo sobre uno de esos duraría más que el universo. Los métodos que lo hacen mejor existen y siguen sin acercarse ni de lejos, que es por lo que el esquema funciona.
Conviene saber
- Los divisores se listan completos hasta sesenta y cuatro; más allá solo se muestra el recuento, porque una página con novecientos números no es algo que lea nadie.
Todas las herramientas de Matemáticas