Números primos

Definición de número primo

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

5, 13, 59.

El número 1 sólo tiene un divisor, por eso no lo consideramos 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, se dice que el número es primo.

Por tanto 179 es primo.

Criba de Eratóstenes

La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos 

menores que un número natural 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 por este algoritmo los números primos menores que 40.

1. Escribimos los números, en nuestro caso serán 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

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

3. El siguiente número es 3, como 3² < 40 eliminamos los múltiplos de 3.

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

4. El siguiente número es 5, como 5² < 40 eliminamos los múltiplos de 5.

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

5. El siguiente número es 7, como 7² > 40 el algoritmo termina y los números que nos quedan son primos.

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

Tabla de números primos

	2	3		5		7				11		13				17		19
		23						29		31						37
41		43				47						53						59
61						67				71		73						79
		83						89								97
101		103				107		109				113
						127				131						137		139
								149		151						157
	163					167						173						179
181										191		193				197		199