Números primos. Crivo de Eratóstenes

A calculadora encontra os números primos utilizando o método "Crivo de Eratóstenes".

Esta calculadora encontra os números primos utilizando um método conhecido desde os tempos antigos como o crivo de Eratóstenes. Vamos lembrar que os números primos não possuem outros divisores, a não ser eles próprios e 1.
Como resultado do trabalho da calculadora, será exibida uma matriz contendo números compostos (cinza) e números primos (preto).

PLANETCALC, Crivo de Eratóstenes

Crivo de Eratóstenes

Crivo
 



Era uma calculadora de demonstração com um algoritmo ingênuo. O intervalo de números é limitado a 1000. A calculadora e seu código-fonte seriam úteis para aquelas pessoas que desejam entender a lógica do antigo cientista Grego que inventou o método no século III a.C.
A calculadora a seguir desenvolve a ideia de Eratóstenes; ela possui uma implementação otimizada para memória e menos operações excessivas. Usando esta calculadora (se o seu computador permitir), você consegue encontrar números primos de até vários bilhões. Entretanto, seja cauteloso - com um limite grande, a memória e o processador do seu dispositivo serão usados ​​sem piedade.

PLANETCALC, Crivo de Eratóstenes, otimizado

Crivo de Eratóstenes, otimizado

Contagem de números primos
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.
Tempo de execução, ms
 
Tempo de saída, ms
 

Todos os números primos encontrados podem ser baixados como um arquivo CSV, mas aqui vou alertá-lo novamente - tudo acontece na memória do seu computador. Ao fazer o download, será usada cinco vezes a quantidade de memória, em comparação com o necessário para armazenar números. Meu antigo laptop com 4GB de RAM conseguiu encontrar facilmente mais de 26 milhões de números primos na faixa de meio bilhão, mas não eu consegui baixá-lo como CSV.

Algoritmo do Crivo de Eratóstenes

O algoritmo em um pseudocódigo:

//Limite
n;
//preencha uma matriz com um (limite superior = n)
a ⟵ [1,1,1,1,1,1,1,1,1,...];
//primeiro loop
para i=2,3,4..≤n:
    se  a[i] = 1:
         //segundo loop
         para j = 2i,3i,4i .. ≤n:
              a[i]⟵0
saída ⟵ todo i no intervalo 2 ≤ i ≤ n, 
    para o qual a condição a[i]=1 é atendida

Otimização do algoritmo

  • como é de fácil visualização, o algoritmo original é passado várias vezes pelos mesmos elementos da matriz, para evitar isso, mudamos o seguinte
    • primeiro loop para i=2,3,4..enquanto i2≤n
    • segundo loop: j=i2,i2+i,i2+2i... ≤n
  • em vez do tipo booleano de 1 byte, podemos usar 1 bit - para reduzir 8 vezes a memória necessária
  • como é de fácil visualização, todos os números pares, exceto 2, não são primos, e levando esse fato em conta, fazemos o seguinte:
    • reduzir a quantidade de memória exigida pela outra metade
    • mudar o algoritmo da seguinte forma:
//primeiro loop
para i=3,5,7..enquanto  i²≤n
    se  a[(i-1)/2] = 1:
         //segundo loop
         para j = i²,i²+2i,i²+4i .. ≤n:
              a[(i-1)/2]⟵0
saída ⟵ 2, todos i ímpares no intervalo: 3 ≤ i ≤ n, 
    para o qual a condição a[(i-1)/2]=1 é atendida
URL copiado para a área de transferência
PLANETCALC, Números primos. Crivo de Eratóstenes

Comentários