Numeros primos n/2 Limite superior

[Raiden]

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.

[MAFUS]

n es el número al que se buscan los primos.
[latex]\frac{n}{\frac{n}{2}} = 2[/latex]
y 2 es el primer primo. Así
[latex]\frac{n}{\frac{n}{2}+1} < 2[/latex]
Por lo que cualquier número por encima de
[latex]\frac{n}{2}[/latex]
salvo n, no dará un número entero y por tanto no es divisible.

[K-YreX]

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:

Código [Seleccionar] Expandir


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:

Código [Seleccionar] Expandir


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:

Código [Seleccionar] Expandir


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.

Código [Seleccionar] Expandir


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í.

[Raiden]

Gracias por responder, me ayudo bastante a entender la cuestion:

Saludos hasta la proxima.