Conteúdo principal
Tempo atual:0:00Duração total:4:12

Transcrição de vídeo

agora vou mostrar um antigo método para gerar uma lista de números primos até o limite e me chamada de crivo de eras tótens era tótens nasceu em 276 antes de cristo então esse método tem mais de dois mil e duzentos anos mas é muito simples e elegante e 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 que se quiséssemos calcular até 10 mil ou 1 bilhão prossiga como é mostrado assuma que todos os números estão desmarcadas cinza é desmarcado começamos no início e se acharmos um número que está desmarcado sabemos que é primo apertamos 2 e dizemos 2 é primo estava desmarcado na segunda fase nós podemos eliminar todos os múltiplos de 2 mas sabemos que eles são compostos então vamos eliminando todos os múltiplos de dois vermelhos composto e agora repetimos agora saímos do 2 para o 3 3 estados marcado então marcamos três como primo e agora eliminamos todos os múltiplos de três e uma simples otimização é note que seja está marca nós marcamos todos os motivos começando com o quadrado daquele número então três vezes três a nove iniciamos 19 e marcamos todos os músculos de três como composto então voltamos até o número 44 está marcado sabemos que é composto anos para o número 5 temos que o número desmarcado então 5 é prime cinco vezes 5 e 25 vamos para 25 camas 25 30 35 40 45 e assim por diante eles todos são compostos dos seguimos até chegar aos 7 sabemos que sete é prima está a desmarcar 77 49 camas 49 e todos os múltiplos de 7 acima deste valor como compostos agora seguimos até marcarmos 1111 é prima nós que onze decisões ea maior que 100 então paramos nesse ponto podíamos até ter parado em dez anos todos os números marcados restantes você vai notar são primos em uma investida podemos marcar todos como pingos e esse é o algoritmo muito simples para generalizar como fazemos isso podemos fazer um programa que faça esse crime queremos achar todos os números primos até o número n primeiro queremos um loop principal então temos para todos os números a de 2 a raiz quadrada de mim note que paramos quando chegamos a 10 mostrei até 11 mas nós paramos pois tinha mostrado todos os prêmios então dois é raiz quadrada de mim seguimos como mostrado cieds marcado sabemos que a e primos e quando chegamos um número primo marcamos todos os múltiplos de ar e seus compostos e pronto então se achar o número primo mas de todos os seus múltiplos volte ao início e incremente a mais um então de dois vão mostrar a 3 e depois para 45 e assim por diante e quando terminarmos teremos todos os prêmios note que aqui também existe um golpe então temos um loop principal para quando acharmos um primo a marcação dos múltiplos também é um loop é importante notar aqui que nós temos um punhado e temos um loop dentro de outro lupi este é um exemplo de um algoritmo em ação escrevi abaixo em java script se colocarmos em aqui estão todos os múltiplos a baixo de sempre se colocarmos 200 aqui estão todos os múltiplos abaixo de 200 se colocar nos 850 aqui estão todos os múltiplos abaixo 850 e aqui embaixo eu tenho um programa com a gravação mostrando como é montado