Factorización prima y divisores
Descomponga N en potencias primas y cuente los divisores
Factorización prima y divisores es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Descomponga N
Todo entero mayor que 1 es un producto único de primos. Encontrar esa descomposición, su factorización en primos, permite resolver muchos problemas de teoría de números. 🧩
La idea de la división de prueba
Extraiga el primo más pequeño que divide a n, divida n entre él y repita. Esta sencilla división de prueba reduce n hasta 1.
Recorra hasta la raíz
Pruebe divisores i mientras i*i sea menor o igual que n. Más allá de la raíz cuadrada, como máximo puede quedar un factor primo.
while i * i <= n:
...Extraiga cada factor
Mientras i divida a n, siga dividiendo y registre i. Así capturará toda la potencia de ese primo antes de continuar.
while n % i == 0:
factors.append(i)
n //= iEl primo restante
Después del bucle, si n sigue siendo mayor que 1, es un factor primo mayor que la raíz cuadrada. Añádalo una vez.
if n > 1:
factors.append(n)La rutina completa
En conjunto, esto produce la factorización en tiempo O(sqrt n) y devuelve cada primo con su multiplicidad completa y en orden.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fAgrupe en potencias
Para contar divisores, necesita cada primo junto con su exponente, como 2^3 en lugar de 2,2,2. Un Counter cuenta las repeticiones de forma sencilla.
from collections import Counter
exp = Counter(factorize(n))La fórmula de los divisores
Si n es p1^a por p2^b, el número de divisores es (a+1) por (b+1). Cada exponente ofrece una opción adicional.
Contar los divisores
Multiplique uno más cada exponente de todos los primos. Así obtendrá el número total de divisores sin tener que enumerarlos.
count = 1
for e in exp.values():
count *= (e + 1)Suma de divisores
Una fórmula relacionada suma los divisores mediante la serie geométrica de cada primo. Conocerla resulta útil para los problemas de números perfectos y de alícuotas.
Acelerar con una criba
Para muchas factorizaciones, precalcule el factor primo más pequeño de cada número con una criba. Después, cada consulta se factoriza en pasos log n.
Comprobación rápida
Aplique la fórmula para contar divisores a un número concreto.
Resumen
Ahora puede factorizar N mediante división por prueba en O(sqrt n), identificar el primo restante, agrupar los exponentes y contar los divisores con la fórmula del producto. ✅
Preguntas frecuentes
¿La lección «Factorización prima y divisores» es gratis?
Sí — el texto completo de «Factorización prima y divisores» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Factorización prima y divisores»?
Descomponga N en potencias primas y cuente los divisores Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Factorización prima y divisores»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- GCD, LCM y el algoritmo de Euclides
- Prueba de primalidad hasta sqrt(n)
- Criba de Eratóstenes
- Factorización prima y divisores