Números primos

Un número primo tiene sólo 2 divisores, él mismo y la unidad.

2, 5, 9, 11, 13...

El número 1 tiene sólo un divisor, por lo que no se le considera número primo.

Para averiguar si un número es primo, se divide ordenadamente por todos los números primos menores que él.

Cuando, sin resultar divisiones exactas, llega a obtenerse un cociente menor o igual al divisor, podemos afirmar que el número es primo.

Ejm

Número primos

Criba de Erastótenes

la Criba de Erastótenes es un algoritmo que permite hallar números primos menores que un número real dado.

  • Partimos de una lista de números que van de 2 hasta un determinado número.
  • Eliminamos de la lista los múltiplos de 2.
  • Luego tomamos el primer número después del 2 que no fue eliminado (el 3) y eliminamos de la lista sus múltiplos, y así sucesivamente.
  • El proceso termina cuando el cuadrado del mayor número confirmado como primo es menor que el número final de la lista.
  • Los números que permanecen en la lista son los primos.

Vamos a calcular, mediante la Criba de Erastótenes los números primos comprendidos entre 2 y 40.

a) En primer lugar escribimos los números, en nuestro caso los comprendidos entre 2 y 40.

    2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40

b) Eliminamos los múltiplos de 2

 2  3  5  7  9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39

c) El siguiente número es el 3, como 32 < 40 eliminamos los múltiplos de 3.

    2  3  5  7
11 13 15 17 19
      23 25 29
      31 35 37

d) El siguiente número es el 5, como 52 < 40 eliminamos los múltiplos de 5.

 2  3  5  7
11 13 17 19
      23 29
      31 37

e) El siguiente número es 7, como 72 > 40, el algoritmo termina, y los números que quedan son primos