Crivo de Eratóstenes

RKA13C Agora vou mostrar um antigo método para gerar uma lista de números primos até o limite "N", chamado de Crivo de Eratóstenes. Eratóstenes nasceu em 276 a.C., então esse método tem mais de 2.200 anos, mas ele é muito simples e elegante, você pode ensinar a qualquer criança. Digamos, por exemplo, que queremos calcular todos os números primos até 100. Isso vai funcionar do mesmo modo do que se quiséssemos calcular até 10 mil ou 1 bilhão. Prossiga como é mostrado. Assuma que todos os números estão desmarcados. Cinza é desmarcado. Começamos do início e, se acharmos um número que está desmarcado, sabemos que é primo. Apertamos 2 e dizemos que 2 é primo, pois está desmarcado. Na segunda fase, nós podemos eliminar todos os múltiplos de 2, pois sabemos que eles são compostos. Então vamos eliminando todos os múltiplos de 2. Vermelho é composto. Agora, repetimos. Agora saímos do 2 para o 3. 3 está desmarcado, então marcamos 3 como primo, e agora eliminamos todos os múltiplos de 3. E uma simples otimização é: note que 6 já está marcado. Nós marcamos todos os múltiplos começando com o quadrado daquele número. Então 3 vezes 3 é 9, iniciamos no 9 e marcamos todos os múltiplos de 3 como composto. Então, voltamos até o número 4. 4 está marcado, sabemos que é composto. Vamos para o número 5. Vemos que é um número desmarcado, então 5 é primo. 5 vezes 5 é 25. Vamos para 25. Marcamos 25, 30, 35, 40, 45... e assim por diante. Eles todos são compostos. Prosseguimos até chegar ao 7. Sabemos que 7 é primo, pois está desmarcado. 7 vezes 7 é 49, marcamos 49 e todos os múltiplos de 7 acima deste valor como compostos. Agora seguimos até marcarmos o 11. 11 é primo. Note que 11 vezes 11 é maior que 100, então paramos neste ponto. Podíamos até ter parado em 10. Todos os números desmarcados restantes, você vai notar são primos. Em uma investida, podemos marcar todos como primos. E este é o algoritmo, muito simples! Para generalizar como fazemos isso, podemos fazer um programa que faça esse crivo. Se queremos achar todos os números primos até o número "N", primeiro, criamos um looping principal. Então temos: para todos os números "a", de 2 à raiz quadrada de "N". Note que paramos quando chegamos a 10. Mostrei até 11, mas nós paramos, pois tinha mostrado todos os primos. Então 2 é a raiz quadrada de "N". Seguimos como mostrado. Se "a" é desmarcado, sabemos que "a" é primo. E, quando chegamos a um número primo, marcamos todos os múltiplos de "a" e seus compostos. Pronto! Então, se achar um número primo, marque todos os seus múltiplos, volte ao início e incremente "a + 1". Então, de 2, vamos para 3 e depois para 4, 5... e assim por diante. E, quando terminarmos, teremos todos os primos. Note que aqui também existe um looping. Então temos um looping principal para quando acharmos um primo. A marcação dos múltiplos também é um looping. É importante notar aqui que nós temos um looping alinhado e temos um looping dentro de outro looping. Este é um exemplo de um algoritmo em ação. Escrevi abaixo em java script. Se colocarmos 100, aqui estão todos os múltiplos abaixo de 100. Se colocarmos 200, aqui estão todos os múltiplos abaixo de 200. Se colocarmos 850, aqui estão todos os múltiplos abaixo de 850. E aqui embaixo eu tenho este programa com a gravação, mostrando como é montado.