Saltar la navegación

E503: ¿Es primo este número?

Conocimiento previo

Un número primo es aquel que solo es divisible entre 1 y por sí mismo. Por ejemplo, el 5 es primo porque solo se puede dividir entre 1 y 5. Pero el 8 no es primo ya que puede dividirse entre 1, 2, 4 y 8. La lista de números primos es infinita y cada año se descubren más gracias a los ordenadores.

Para saber si un número, n, es primo hay que dividir ese número entre todos los números comprendidos entre 1 y n y ver si alguno da la división exacta.

Para saber si la división es exacta se usa el operador %. Este operador nos da el resto de una división, por lo tanto, si a%b es 0 es que la división es exacta y el número a es divisible entre b, si da cualquier otra cosa es que no es divisible. Esto nos permite saber muy fácilmente si un número es divisible o no entre otro.

Prueba esto en el terminal de repl.it:

Como puedes ver cuando la división da exacta da 0 y cuando no es exacta da otro número.

Actividad

  • La siguiente función esprimo(x) devuelve True si x es primo y False si x no lo es.
  • El bucle for dará valores a i desde 2 hasta x-1 para ver si x es divisible entre alguno de los números.
  • En la línea 4 se comprueba si al dividir x entre estos números da exacto, si da exacto se acaba la función y se devuelve False (no es primo)
  • Si el bucle se termina sin ninguna división exacta entonces es que el número es primo y se devuelve True en la línea 7.
  • En las líneas 10 a 12 se pone a prueba la función con unos cuantos números. Puedes probar otros si quieres.

Aunque este programa funciona a la perfección es muy poco eficiente. Con números primos altos tarda mucho tiempo. Vamos a mejorarlo.

Una forma de hacerlo es eliminando la mitad de los números, es decir quitar los números pares. Eso hará que el programa tarde la mitad de tiempo.

Miramos si x es divisible entre 2 y si no lo es haremos que range tome solo valores impares, empezando por el 3 (eso se hace añadiendo un tercer parámetro que es cada cuanto se cogen los números, ver línea 8). Si es divisible entre dos hay dos posibilidades: Es el número 2, con lo cual sí que es primo, o es un múltiplo de 2, con lo cual no es primo. Deberemos tener esto en cuenta.

Todavía podemos mejorarlo más, en lugar de comprobar si es divisible entre todos los números de 2 a x-1, en realidad bastará con hacerlo entre 2 y la parte entera de \(\sqrt x \)