Los factores primos de 13195 son 5, 7, 13 y 29.
¿Cuál es el mayor factor primo de 600851475143?
¿Qué es un factor primo?
Un factor de N es un número que divide a N exactamente. Un factor primo es un factor que además es primo (solo divisible por 1 y por sí mismo).
Factorizando 13195 a mano
¿Es divisible por 2?
13195 es impar → No es divisible por 2
¿Es divisible por 3?
1+3+1+9+5 = 19, no es múltiplo de 3 → No
¿Es divisible por 5?
Termina en 5 → Sí! 13195 ÷ 5 = 2639
Ahora factorizamos 2639
2639 ÷ 7 = 377 → Sí!
Factorizamos 377
377 ÷ 13 = 29 → 29 es primo!
El problema real
600851475143 es demasiado grande para factorizar a mano. Necesitamos un algoritmo eficiente.
Conceptos clave
La estrategia
Dividir N por cada número empezando desde 2. Cuando encontramos un divisor, lo dividimos tantas veces como sea posible y seguimos. El último divisor encontrado es el mayor.
Truco clave: No necesitamos verificar si el divisor es primo. Si dividimos todos los 2, luego todos los 3... cuando lleguemos a 4, ya no habrá factores de 4 (porque ya quitamos los 2). Los compuestos nunca dividen.
Variante A: while True + break
Bucle infinito que termina cuando N queda reducido a 1. Muy explícita en cada paso.
Variante B: while con condición
La condición de salida va en el while. Más limpia, sin break.
Variante C: con while anidados
Un while interno elimina todas las ocurrencias de cada factor. Más estructurada.
¿Cuál elegir?
| Variante | Líneas | Ventaja | Cuándo usarla |
|---|---|---|---|
| A: while True + break | 12 | Muy explícita | Para entender el algoritmo |
| B: while con condición | 9 | Compacta | Uso general |
| C: while anidados | 11 | Muestra factores | Debug / aprendizaje |
Conceptos clave
n % divisor == 0
Test de divisibilidad. Si el resto es 0, divisor divide exactamente a n.
n // divisor
División entera. Descarta la parte decimal. 7 // 2 = 3, no 3.5
¿Por qué no incrementar cuando divide?
Un número puede tener el mismo factor varias veces. Ej: 12 = 2 × 2 × 3. Debemos dividir por 2 dos veces.
divisor += 1
Incremento. Equivale a divisor = divisor + 1. Forma abreviada común en Python.
f"texto {variable}"
f-string. Permite insertar variables dentro de texto. La f antes de las comillas lo activa.
Conceptos de Python aprendidos
Función reutilizable
Encapsulamos la lógica en una función que devuelve todos los factores primos,
y usamos max() para obtener el mayor.
Desglose
def factores_primos(n):
Definimos una función que recibe n y devuelve sus factores.
factores.append(d)
Cada vez que encontramos un divisor, lo añadimos a la lista.
n //= d
Equivale a n = n // d. División entera con asignación.
max(primos)
Función integrada que devuelve el valor máximo de un iterable.
| Aspecto | Fuerza bruta | Pythónico |
|---|---|---|
| Resultado | Solo el mayor | Todos los factores |
| Reutilización | Código inline | Función importable |
| Memoria | O(1) | O(log n) |
Conceptos aprendidos
Optimización: solo hasta √n
Observación clave: Si n tiene un factor primo p > √n, entonces n/p < √n. Es decir, el otro factor sería menor que √n y ya lo habríamos encontrado.
¿Por qué funciona?
√600851475143 ≈ 775146
En vez de probar hasta 600 mil millones, probamos hasta ~775 mil.
Si queda n > 1 al final
Ese n restante es primo (no tiene factores ≤ √n, por tanto no tiene factores propios).
Comparativa de rendimiento
| Método | Iteraciones máx | Para n = 10¹² | Complejidad |
|---|---|---|---|
| Fuerza bruta | ~n | 10¹² ops | O(n) |
| Optimizado √n | ~√n | 10⁶ ops | O(√n) |
La optimización reduce las iteraciones de 600 mil millones a ~775 mil. Un millón de veces más rápido.