Realmente si no eres capaz de relacionarlo se podría decir que vas bien pues en caso de encontrar tal relación, estarías equivocado.
Todo esto viene a raíz de (no lo hice a propósito
) del siguiente ejercicio típico o cualquiera de sus variantes:
Crea un programa que, dado un número entero positivo n, determine si es o no primo.
Como tú y yo sabemos, un número primo es aquel que solo se puede dividir por uno mismo y la unidad (1), por ejemplo: 2, 3, 5, 7... (el 1 en la mayoría de casos no es considerado como un número primo pero eso da para otro tema por lo que lo dejaremos ahí)
La solución más básica y menos eficiente (llamémosla: el cerdito que hizo la casa de paja) sería calcular todos los divisores de n y ver si son 2 o más:
divisores := 0
PARA i := 1 HASTA n HACER
SI n % i == 0 ENTONCES
divisores := divisores + 1
FIN SI
FIN PARA
SI divisores == 2 ENTONCES
El numero n SI es primo
SINO
El numero n NO es primo
FIN SI
Pero un día el hermano del anterior (el cerdito que hizo la casa de madera) dijo:
Si ya tenemos más de 2 divisores, para qué vamos a seguir comprobando?
y creó algo mejor:
i := 1
divisores := 0
MIENTRAS i <= n && divisores <= 2 HACER
SI n % i == 0 ENTONCES
divisores := divisores + 1
FIN SI
i := i + 1
FIN MIENTRAS
SI divisores == 2 ENTONCES
El numero n SI es primo
SINO
El numero n NO es primo
FIN SI
Pero entonces el mayor de los 3 (el cerdito que hizo la casa de piedra), que era bueno en matemáticas porque era arquitecto por lo menos, dijo:
- Un número primo es aquel que únicamente puede expresarse como producto de 2 números naturales: n = a * b donde a = 1 y b = n o a la inversa (por la propiedad conmutativa del producto).
- Siempre 1 <= a, b <= n (a y b estarán en el rango [1,n]).
- Todo coeficiente a tendrá un coeficiente complementario b que se calcula como: b = n / a.
Entonces: Existe un punto medio x que cumple: (1 <= a <= x) y (x <= b <= n) teniendo como premisa a <= b (sin darles la vuelta a a y b). Lo que significa que solo hay que buscar algún valor que cumpla las condiciones de a para saber que existirá un b. Por lo que solo habrá que buscar en el rango [1, x] y no en el rango [1, n].
Entonces: Como a y b siempre están en el rango [1, n], el punto medio es x = n/2.
y diseñó lo que parecía la mejor solución de todas:
i := 1
divisores := 0
MIENTRAS i <= n/2 && divisores <= 2 HACER
SI n % i == 0 ENTONCES
divisores := divisores + 1
FIN SI
i := i + 1
FIN MIENTRAS
SI divisores == 1 ENTONCES // 1 porque no vamos a llegar hasta n que también es divisor
El numero n SI es primo
SINO
El numero n NO es primo
FIN SI
Los dos cerditos menores quedaron asombrados y fueron los 3 juntos a comercializar "el mejor algoritmo del mundo para encontrar números primos". Pero justo cuando iban a conseguir el reconocimiento mundial, apareció el lobo que era todavía mejor en matemáticas que el cerdito arquitecto y dijo:
Con todo lo anterior, el valor más grande de a es aquel que cumple que a = x. En tal caso, b tiene que valer su valor más pequeño que también es x.
Entonces: n = a * b se podría expresar como n = x * x. Un número x que multiplicado por si mismo da n, y esto hace referencia a la definición de raíz cuadrada de n.
Entonces: x no es n/2. x = sqrt(n). sqrt significa raíz cuadrada: square root.
Con esto el lobo mejoró el algoritmo del cerdito mayor y dejó a los 3 hermanos sin su ansiada recompensa.
i := 1
divisores := 0
MIENTRAS i <= sqrt(n) && divisores <= 1 HACER
SI n % i == 0 ENTONCES
divisores := divisores + 1
FIN SI
i := i + 1
FIN MIENTRAS
SI divisores == 2 ENTONCES
El numero n SI es primo
SINO
El numero n NO es primo
FIN SI
Todos estos códigos pueden ser implementados en muchos lenguajes de programación, entre ellos C++.
Así es como C++, los números primos, n/2, sqrt(n) y la fábula de los 3 cerditos están todos relacionados entre sí.
Autor
.png)
En línea
