O Crivo de Eratóstenes

Crivo de Eratóstenes

        O crivo de Erastóstenes é um método simples que nos permite encontrar todos os números primos até o número que escolhermos, separando gradativamente o conjunto de todos os números inteiros aqueles que são primos.

        Etapas do algoritmo:

Liste todos os números inteiros de 2 até o valor limite: 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 e 35.

Encontre o primeiro número da lista, este é um número primo.

Exclua da lista todos os múltiplos do número primo encontrado (4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34).

O próximo número da lista é primo, exclua novamente na lista todos os múltiplos do número primo encontrado (9, 15, 21, 27, 33).

O número em seguida também é primo, exclua todos os múltiplos do mesmo (25,35).

Restarão os números 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 e 31, estes são os números primos num conjunto de números de 2 a 35.  . . .

        Sendo assim concluímos que os números anteriores são numero primos, e não primos.

        

A seguir um exemplo do que foi redigido anteriormente, pode-se entender que, todos os campos que não contem fundo preto são os números primos.

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

        

        

...