mientras que (i <= sqrt (static_cast (n))

Question

En la "C ++ sin miedo: una guía para principiantes que te hace sentir inteligente" libro, en el capítulo (2): Decisiones, Decisiones, se puede ver este lin de código como parte del programa de números primos:

while (i<=sqrt(static_cast<double>(n))

A condición de que "i" se ha inicializado a "2", y "n" es la entrada del usuario.

¿Por qué estamos comparando a la "raíz cuadrada" de "n" y no a "n" en sí?

Gracias.

Answer 1

Porque si un número tiene factores distintos de la misma y 1, entonces al menos uno de esos factores será menor que sqrt del número.

Answer 2

Debido a que usted no recibirá factores para no primos que son> sqrt (n) (que ya habría encontrado el otro factor, más pequeño).

Es una prueba muy mal, sin embargo, sería mucho mejor escribir como:

while (i*i <= n)

Answer 3

while (i<=sqrt(static_cast<double>(n))

Es equivalente a

while(n >= i*i)

¿Por qué el autor elija la primera solución puede depender de otras partes del código.

Answer 4

El código es el siguiente:

i = 2;
while (i <= sqrt(static_cast<double>(n)) {
  if (n % i == 0) is_prime = false;
  i++;
}

Así que el bucle está comprobando si n es divisible por i sin resto. Obviamente, sólo se tiene que comprobar esto hasta (e incluyendo) la raíz cuadrada de n (porque si n / p = q entonces también n / q = p).

Answer 5

Algorithmically es correcto para comprobar posibles factores hasta la raíz cuadrada de su objetivo.

Si N es un número que puede o no puede ser primer, si no existen factores (no incluyendo 1) hasta sqrt (N), entonces N debe ser primer. sqrt (N) en sí bien puede ser su único factor primordial (por ejemplo, 9, que es 3 * 3).

Si vamos a prueba para ver si el 17 es un número primo, sabemos que sqrt (17) está justo por encima de 4. 2, 3 y 4 no se dividen en 17 por lo que debe ser primer como 5 es mayor.

Esto debe ser el caso, porque 17/5 será inferior a 5 y tendría que ser un factor también, pero sabemos que no hay factores menos de 5.

mediante programación, por supuesto, el código no es óptima, ya que no se usará dobles y cuadrados de base sino algo así como (i * i <= N)