Crivo de Eratóstenes

O crivo de eratóstenes é utilizado para determinar os números primos presente numa lista de números fixados.

Estabelecemos uma lista de números de 1 a 100, para exemplificar o método

1	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
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Lembrete: o 1 não é primo, pois seu único divisor é ele mesmo. Logo o cortamos da tabela.

o método consiste em cortar os números que não são primos, até restar somente os números primos.

Para isso pegasse o primeiro primo e elimina todos os seus múltiplos da lista, assim obtemos:

	2	3		5		7		9
11		13		15		17		19
21		23		25		27		29
31		33		35		37		39
41		43		45		47		49
51		53		55		57		59
61		63		65		67		69
71		73		75		77		79
81		83		85		87		89
91		93		95		97		99

observe que o único numero primo par é o 2.

o próximo primo é o numero 3, assim nós o mantemos e eliminamos todos os múltiplos de 3

	2	3		5		7
11		13				17		19
		23		25				29
31				35		37
41		43				47		49
		53		55				59
61				65		67
71		73				77		79
		83		85				89
91				95		97

e assim sucessivamente até chegar em um primo que não possui múltiplos na lista, cortando os múltiplos de 5:

	2	3		5		7
11		13				17		19
		23						29
31						37
41		43				47		49
		53						59
61						67
71		73				77		79
		83						89
91						97

cortando os múltiplos de 7:

	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

Depois do 7, o próximo primo é o número 11, e na lista já não contém nenhum múltiplo de 11, assim termina-se o processo do crivo e os números restantes na lista são os primos de 1 a 100.

portanto os primos entre 1 e 100 são: {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}.