If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Teste de primalidade com crivo

Uma tentativa de otimizar o teste de primalidade com divisão por tentativas usando o Crivo de Eratóstenes. Versão original criada por Brit Cruise.

Quer participar da conversa?

Nenhuma postagem por enquanto.
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.

Transcrição de vídeo

RKA4JL - Recapitulando: Estamos checando se um número N é primo através da divisão por testes. Aqui nós temos a raiz quadrada de N e aqui 3. Começando no 3, nós vamos pulando de dois em dois até a raiz quadrada de N. E a cada ponto passado, vamos checando se o número é divisível por N. Há tempos temos tentado diminuir o número de passos que damos, talvez começando mais adiante e dando passos maiores. Quero parar nesse ponto um pouquinho e pensar o que é o ideal neste caso para o algoritmo ou o método de divisão por tentativas. Qual é a melhor possibilidade de encontrar primos se fôssemos muito criativos em nossos passos? Lembre-se que todo número N tem o fator 3. Vamos dizer que a raiz quadrada de N é aqui. Precisamos passar apenas pelos números primos. Isso seria o melhor que poderíamos fazer porque sabemos que se passarmos apenas por primos, vamos eventualmente encontrar o fator. Um fator 3 ou seu múltiplo. Agora, a pergunta é: "quão eficiente é esse método?" Porque parece que estamos diante de uma solução perfeita neste momento. E se escrevermos um novo algoritmo chamando ele, primeiramente, de algoritmo com crivo? Digamos que este algoritmo calcula se o número N é primo. Se a gente chamar esse crivo, ele vai gerar uma longa lista de números primos e, então, teremos a nossa divisão por tentativas, que poderia usar essa lista de números primos. Ela, então, pularia apenas nos números primos até raiz quadrada de N, seja qual for. Então, qual é o problema nisso? Nós podemos visualizar a complexidade temporal disso ou o número de passos dados no processo. Lembre-se de que isso já foi feito: foi indicado no algoritmo de primalidade e nele foi colocado um contador de passos dentro dos loops. Temos um passo "mais mais", que significa "passo mais 1", aqui. E dentro deste outro loop também é um contador de passos "mais mais". São operações constantes checando e marcando os números. Então, nós temos um contador de passos dentro dos loops e podemos dar uma olhada em uma comparação aqui. No canto esquerdo, nós temos o método de divisão por tentativas. No meio, o algoritmo que criamos. Nós criamos o crivo para gerar os números primos até N. E, na direita, a proposta com crivo para gerar números primos até a raiz quadrada de N e depois fazer a divisão por tentativa nesses números primos. Vamos ver o que acontece com uma amostra pequena. Vemos que, com o crivo, ele começa dando muitos passos. Até a versão modificada mais à direita, ela é mais devagar do que a divisão por tentativas. À medida que a amostra aumenta, os passos com o crivo ficam mais rápidos. Vamos esquecer o método do meio e comparar os outros dois, ou seja, a divisão por tentativa e a divisão com o crivo até a raiz quadrada de N mais a divisão por tentativas. Nós podemos ver que a divisão por tentativas é muito mais eficiente: o número de passos com crivos até a raiz quadrada vai aumentando muito rápido. Então, não há uma melhora em colocar um segundo passo. Aqui embaixo está o programa que eu usei para fazer essa comparação e ele está gravado em uma explicação de como isso foi programado. Agora, você deve estar pensando: "bom, e se calcularmos os primos antes?" Então, o primeiro passo seria criar uma lista de números primos e guardá-los em uma memória, tipo um HD. Aí, o algoritmo teria que rodar a divisão por tentativas e saberia como passar apenas pelos primos porque ele estaria lendo a partir dessa lista de números primos gerados. Talvez essa lista armazene números primos de até vinte dígitos ou até mesmo de cem dígitos. Mas por que a gente não pode fazer isso? O problema é a limitação de memória. Quando temos inúmeras listas de números, a gente tem um probleminha. Por exemplo, vamos pensar que estamos fazendo isso à mão. Calculamos e vemos que 5 é primo. Escrevemos em um papel e guardamos em um arquivo. Calculamos e vemos o 7. Guardamos no arquivo. Chegamos ao 9... Não, desculpa. Ao 11. E guardamos no arquivo. Teremos um arquivo cheio de números primos. Pense nele como uma lista de números primos. Quão grande teria de ser esse arquivo se quiséssemos armazenar números com até vinte dígitos? Ou até números com cem dígitos? Nós poderíamos arquivar essa lista no HD. Para entender por que isso não é possível, é preciso mergulhar mais a fundo em como isso cresce, essa lista de números, qual é a limitação de memória e de espaço nos tempos modernos e até como isso afetará computadores no futuro.