Prueba de primalidad hasta sqrt(n)
Compruebe un solo número de forma eficiente
Prueba de primalidad hasta sqrt(n) es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 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 Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
La pregunta sobre los primos
Una habilidad matemática fundamental consiste en decidir si un número es primo. Un número primo tiene exactamente dos divisores: uno y él mismo. Vamos a comprobarlo rápidamente. 🔍
La comprobación ingenua
Podría intentar dividir n entre todos los números desde 2 hasta n menos 1. Es correcto, pero resulta terriblemente lento cuando n es grande.
El truco de la raíz cuadrada
Esta es la idea clave: solo necesita comprobar divisores hasta la raíz cuadrada de n. Más allá de ese punto no puede aparecer ningún factor nuevo.
Por qué basta la raíz cuadrada
Los divisores aparecen en pares cuyo producto es n. Si ambos estuvieran por encima de la raíz cuadrada, su producto superaría n, lo cual es imposible.
El límite del bucle
Itere i desde 2 mientras i por i sea menor o igual que n. Usar i*i evita el error de coma flotante de sqrt con enteros grandes.
while i * i <= n:
...Gestione los casos pequeños
Los números menores que 2 nunca son primos, así que rechácelos de antemano. Esta comprobación mantiene el bucle principal limpio y correcto.
if n < 2:
return FalseLa función completa
Reúna todos los pasos: compruebe primero los valores pequeños y, después, recorra los posibles divisores hasta la raíz. Cualquier división exacta significa que n es compuesto.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return TrueAcelérelo
Compruebe el 2 por separado y, después, pruebe únicamente números impares. Omitir los pares aproximadamente reduce a la mitad el trabajo sin añadir complejidad.
if n % 2 == 0:
return n == 2El coste temporal
Esta prueba se ejecuta en tiempo O(sqrt n). Para un solo número de hasta mil millones, eso supone apenas unas 30 000 operaciones sencillas.
Un número, no muchos
La prueba de la raíz cuadrada es ideal para una o unas pocas consultas. Si necesita comprobar la primalidad de todo un rango, una criba será mucho más rápida.
Evite el error de la raíz cuadrada
Comparar con i*i en lugar de usar math.sqrt evita los errores de redondeo que podrían aceptar o rechazar incorrectamente números límite.
Comprobación rápida
Confirme el límite que hace rápida esta prueba.
Repaso
Ahora puede comprobar si un número es primo en tiempo O(sqrt n), gestionar los valores pequeños, omitir los pares y usar i*i para mantener la exactitud. ✅
Preguntas frecuentes
¿La lección «Prueba de primalidad hasta sqrt(n)» es gratis?
Sí — el texto completo de «Prueba de primalidad hasta sqrt(n)» 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 Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Prueba de primalidad hasta sqrt(n)»?
Compruebe un solo número de forma eficiente Practicas Coding Interview Prep 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 Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep 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 2 de 4.
¿Cuánto tiempo toma la lección «Prueba de primalidad hasta sqrt(n)»?
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 Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep 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