Título: Numeros primos n/2 Limite superior
Publicado por: Raiden en 23 Agosto 2021, 14:21 pm
Hola a todos,
Eh estado haciendo unos ejercicios sobre funciones y me encontre con una consigna que no logre entenderla.
Dice "Al principio podria pensarse que n/2 es el limite superior para evaluar si un numero es primo. pero lo máximo que se necesita es ir hasta la raíz cuadrada de n, Por que?"
Lo de la raiz pude entenderlo pero sobre lo de n/2 ¿como se llega a relacionar con los numeros primos y c++? ya he buscado por internet pero no encuentro nada.
Gracias por cualquier aporte. ::)
Saludos.
Eh estado haciendo unos ejercicios sobre funciones y me encontre con una consigna que no logre entenderla.
Dice "Al principio podria pensarse que n/2 es el limite superior para evaluar si un numero es primo. pero lo máximo que se necesita es ir hasta la raíz cuadrada de n, Por que?"
Lo de la raiz pude entenderlo pero sobre lo de n/2 ¿como se llega a relacionar con los numeros primos y c++? ya he buscado por internet pero no encuentro nada.
Gracias por cualquier aporte. ::)
Saludos.
Título: Re: Numeros primos n/2 Limite superior
Publicado por: MAFUS en 23 Agosto 2021, 18:57 pm
n es el número al que se buscan los primos.
y 2 es el primer primo. Así
Por lo que cualquier número por encima de
salvo n, no dará un número entero y por tanto no es divisible.
y 2 es el primer primo. Así
Por lo que cualquier número por encima de
salvo n, no dará un número entero y por tanto no es divisible.
Título: Re: Numeros primos n/2 Limite superior
Publicado por: K-YreX en 23 Agosto 2021, 19:03 pm
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 :rolleyes:) del siguiente ejercicio típico o cualquiera de sus variantes:
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:
Pero un día el hermano del anterior (el cerdito que hizo la casa de madera) dijo:
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:
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:
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í.
Todo esto viene a raíz de (no lo hice a propósito :rolleyes:) del siguiente ejercicio típico o cualquiera de sus variantes:
Citar
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:
Código:
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
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:
Citar
Si ya tenemos más de 2 divisores, para qué vamos a seguir comprobando?
y creó algo mejor:Código:
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
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:
Citar
- 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:- 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.
Código:
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
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:
Citar
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.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.
Código:
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
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í.
Título: Re: Numeros primos n/2 Limite superior
Publicado por: Raiden en 24 Agosto 2021, 14:42 pm
Gracias por responder, me ayudo bastante a entender la cuestion:
Saludos hasta la proxima. :D
Saludos hasta la proxima. :D