Algoritmos: primalidad y la ecuación cuadrática

Objetivos

1. Escribir un algoritmo de primalidad por prueba de divisores hasta la raíz cuadrada.
2. Aplicarlo a 29 y a 35 con las divisiones hechas, no solo con el veredicto.
3. Resolver x² − 5x + 6 = 0 por la fórmula y, como algoritmo alternativo, por factorización.
4. Dejar por escrito en el editor uno de los dos y una variante.

Explicación

Qué es un algoritmo aquí

Un algoritmo es una lista finita de pasos que termina y que otra persona puede repetir sin adivinar. No hace falta un lenguaje de programación: el editor de esta página es papel. Lo que no vale es «mirar si se ve primo».

Primalidad por divisores

Para un entero n > 1: recorre los enteros d desde 2 hasta el mayor entero cuyo cuadrado no pasa de n. Si alguno divide a n, n es compuesto y paras. Si ninguno divide, n es primo. Basta llegar a la raíz porque, si n = a · b y a es mayor que la raíz, entonces b es menor que la raíz y ya lo habrías visto.

El tope del algoritmo no es un número redondo: es el mayor entero d tal que d² ≤ n. Si n es un cuadrado perfecto, ese entero divide a n y hay que probarlo. Parar uno antes declararía primo a un cuadrado que solo se factoriza con su raíz. Con 49, los divisores propios son 7 y 7. Si te quedas en d = 6, ninguna división entera ha salido exacta y el criterio, mal cortado, diría «primo». No lo es: 7² = 49. El caso fácil, como 35, para pronto porque aparece un divisor pequeño; el caso que enseña el tope es el que no tiene divisor pequeño.

En la ecuación de segundo grado el algoritmo también tiene un corte: el signo del discriminante. D > 0, dos raíces reales distintas; D = 0, una raíz doble; D < 0, ninguna raíz real. No se «redondea D a cero» si sale 1, ni se ignora el cero si sale exacto. Y el numerador es −b, no b: con b = −5, −b vale 5. Escribir b en el numerador cambia el signo de las dos raíces.

Ejemplo 1 · 29 es primo y 35 no

Para 29, √29 está entre 5 y 6 porque 5² = 25 y 6² = 36. Hay que probar d = 2, 3 y 5.

1. 2 · 14 = 28
   28 + 1 = 29
   29 = 29. No divide.
2. 3 · 9 = 27
   27 + 2 = 29
   29 = 29. No divide.
3. 5 · 5 = 25
   25 + 4 = 29
   29 = 29. No divide.

29 es primo.

Para 35, √35 está entre 5 y 6 (25 < 35 < 36). Pruebas:

1. 2 · 17 = 34
   34 + 1 = 35
   35 = 35. No.
2. 3 · 11 = 33
   33 + 2 = 35
   35 = 35. No.
3. 5 · 7 = 35
   35 + 0 = 35
   35 = 35. Sí: 5 · 7 = 35.

35 es compuesto. El algoritmo para en el 5; no hace falta seguir.

Ejemplo 2 · Algoritmo alternativo, la ecuación cuadrática

Ecuación x² − 5x + 6 = 0, con a = 1, b = −5, c = 6.

Algoritmo de la fórmula. Discriminante D = b² − 4ac = 25 − 24 = 1. Como D > 0 hay dos raíces reales:

x = (5 ± 1) / 2. Entonces x₁ = 6/2 = 3 y x₂ = 4/2 = 2.

Algoritmo alternativo: buscar el factor. Dos números que sumen 5 y multiplicados den 6: 2 y 3. Luego (x − 2)(x − 3) = x² − 5x + 6. Las raíces son otra vez 2 y 3.

Comprobación en la ecuación: 2² − 5·2 + 6 = 4 − 10 = −6
−6 + 6 = 0 y 3² − 5·3 + 6 = 9 − 15 = −6
−6 + 6 = 0.

Ejemplo 3 · 49 no es primo, y una cuadrática con discriminante 0

Dos algoritmos cortos, con la cuenta escrita, para ver el corte de la raíz y el corte del discriminante.

1. Paso 1. √49 = 7 exacto, porque 7² = 49 y 6² = 36 < 49. El algoritmo incluye d = 7. No se detiene en 6.
2. Paso 2. En x = 0, ŷ = 7/6 y el residuo es 1 − 7/6 = −1/6.
   En x = 1:
   (1/2) · 1 = 1/2
   1/2 + 7/6 = 10/6
   10/6 = 5/3
   El residuo es 2 − 5/3 = 1/3.
   En x = 2, ŷ = 1 + 7/6 = 13/6 y el residuo es 2 − 13/6 = −1/6.
3. Paso 3. Ecuación x² − 8x + 16 = 0, con a = 1, b = −8, c = 16.−8 · −8 = 64
   4 · 1 = 4
   4 · 16 = 64
   64 − 64 = 0
   D = 0. Una raíz doble: x = 8/2
   8/2 = 4. Sustitución: 4 · 4 = 16
   8 · 4 = 32
   16 − 32 = −16
   −16 + 16 = 0. Factorización: (x − 4)² = x² − 8x + 16. Los dos algoritmos, fórmula y factor, dan el mismo 4.

Si en el paso 3 se toma b = 8 en el numerador, (8 ± 0)/2 = 4 sigue saliendo por casualidad, porque −b y |b| coinciden cuando b es negativo y la raíz es doble y positiva. No es un permiso para cambiar el signo en general. En el ejemplo 2, b = −5 y D = 1: usar b en vez de −b produce −2 y −3, y ninguno anula x² − 5x + 6. El caso D = 0 de este ejemplo no esconde ese fallo; el ejemplo 2 sí lo enseña.

Suma de control del primo: 7 · 7 = 49, y 49 no es 7 · 8. 7 · 8 = 56. Quien «acerca» 49 a 56 para usar el 8 ya no está ejecutando el algoritmo: está cambiando el número.

Comprobación cruzada · 121 y una cuadrática con D distinto de 0 y de 1

121 es otro cuadrado, para no quedarse en el 49. 11² = 121 y 10² = 100, así que el algoritmo llega hasta d = 11. Restos: 121 = 2·60 + 1;3 · 40 = 120
120 + 1 = 121
121 = 121;5 · 24 = 120
120 + 1 = 121
121 = 121; 121 = 7·17 + 2 (porque 7·17 = 119);8 · 15 = 120
120 + 1 = 121
121 = 121;121 = 9·13 + 4 (9·13
9·13 + 4 (9·13 = 117);11 · 11 = 121
121 + 0 = 121
121 = 121. Para en el 11. Es compuesto. Quien pare en 10, con todos los restos distintos de 0, declararía primo a 121.

Ecuación distinta de las anteriores: x² − 3x − 10 = 0, a = 1, b = −3, c = −10.4 · 1 = 4
4 · (−10) = −40
9 − −40 = 49
D = 49. √49 = 7. x = (3 ± 7)/2. x₁ = 10/2 = 5 y x₂ = (−4)/2 = −2. Sustitución: 5 · 5 = 25
3 · 5 = 15
25 − 15 = 10
10 − 10 = 0;−2 · −2 = 4
3 · (−2) = −6
4 − −6 = 10
10 − 10 = 0. Factorización: (x − 5)(x + 2) = x² − 3x − 10. El signo de c es negativo y por eso una raíz es negativa. No se tira: anula el polinomio.

Otro entero, el 89, para ver un primo con todos los restos escritos, sin usar el 91 del reto. 9² = 81 y 10² = 100, luego √89 cae entre 9 y 10 y hay que probar d de 2 a 9.

Ningún resto es 0, así que 89 es primo. Parar en d = 7, aunque el resto sea 5, dejaría sin mirar el 8 y el 9. El algoritmo no acaba cuando un resto «ya es pequeño»: acaba cuando se agota el intervalo o cuando un resto es 0.

77, compuesto, con parada en el 7

77 no es el 91 del reto. √77 está entre 8 y 9, porque 8² = 64 y 9² = 81. El algoritmo puede parar antes si aparece un divisor.2 · 38 = 76
76 + 1 = 77
77 = 77; 77 = 3·25 + 2 (75+2);5 · 15 = 75
75 + 2 = 77
77 = 77;7 · 11 = 77
77 + 0 = 77
77 = 77. Para en el 7: 77 = 7·11. No hace falta probar el 8. Comparado con el 89, donde ningún resto fue 0 y hubo que llegar al 9, aquí el criterio acaba en cuanto el resto es cero. Las dos salidas —«primo» y «compuesto»— salen del mismo algoritmo.

Error típico

Probar solo el 2, el 3 y el 5 en el 35 y, al ver que 2 y 3 no dividen, declarar primo sin llegar al 5. O, en la fórmula, tomar b = 5 en vez de b = −5 y calcular D = 25 + 24. Aquí el término −4ac usa b², que es (+25) igual, pero el numerador es −b, no b: si escribes (b ± √D) / 2 con b = −5 obtienes números negativos que no anulan el polinomio.

Tu desarrollo

En el editor, escribe el algoritmo de primalidad o el de la cuadrática, y debajo una versión alternativa (la factorización, o probar divisores solo entre los primos hasta la raíz). El rótulo inicial se puede borrar.

Comprueba

Cierre

Un algoritmo se puede ejecutar a mano. 29 no tiene divisor hasta su raíz, luego es primo. 35 = 5 · 7, luego no lo es. La ecuación x² − 5x + 6 = 0 da 2 y 3 por la fórmula y también por la factorización.