[Tutorial] O que é o Crivo de Eratosthenes?

[saramgsilva]

Como consequência de vários tópicos que falarem na procura de números primos, venho falar num método muito simples para encontrar números primos

O Crivo de Eratosthenes

O algoritmo do Crivo de Eratosthenes possui um único argumento k, que é um número inteiro. Ao final de sua execução obtemos uma lista com todos os números primos inferiores ou igual a k é retornada.

Sequencialmente, escreve-se todos os inteiros de 2 até k.

Risca-se então todos os números maiores que 2 que são divisíveis por 2. No próximo passo, selecciona-se (de entre os números não riscados) o menor número que é superior a 2.

Neste caso, esse número é o 3. Assim, risca-se todos os números maiores que 3 que são por ele divisíveis.

O processo então recomeça, desta vez o menor número maior que 3 e não riscado é o 5.

Portanto, risca-se todos os inteiros maiores que 5 que são por ele divisíveis.

Continua-se a fazer este procedimento até que todos os números divisíveis por tenham sido riscados. Os números restantes que não foram riscados são todos primos: 2, 3, 5, 7, 11, 13,…

Visualização do crivo:

Pode obter mais informações em :

Wikipedia PT -Crivo de Eratosthenes

projetozk -Crivo de Eratóstenes

Criptografia - CRIVO DE ERASTÓTENES E DIVISÃO POR TENTATIVA

Números Primos

[Artigo no Wiki]

[UnKnowN]

Muito Obrigado Tofas já percebi 👍

[Triton]

Quem quiser pesquisar, tem aqui um link para o Crivo de Atkin, uma técnica mais eficiente ainda.

http://en.wikipedia.org/wiki/Sieve_of_Atkin

[brink@ero]

O algoritmo do Crivo de Eratosthenes

Muito bom, não conhecia. Mas sendo isto um algoritmo, vai para a secção dos algoritmos  😛

Cumpr. brink@ero  👍

[mogers]

é um algoritmo muito útil. Eu por acaso antes de o conhecer criei-o... pensei na mesma coisa...  só é problematico quando são números muito grandes e não temos memória para o usar (no caso de um concurso de programação ou outra coisa qualquer, onde a memória do programa é limitada).

[vbmaster]

Deve ser uma maneira muito mais rápida e eficiente de achar número primos que o meu programazinho da baba em c++.... 👍

Hei de tentar implementá-lo e comparar tempos... 😛

[Warrior]

é um algoritmo muito útil. Eu por acaso antes de o conhecer criei-o... pensei na mesma coisa...  só é problematico quando são números muito grandes e não temos memória para o usar (no caso de um concurso de programação ou outra coisa qualquer, onde a memória do programa é limitada).

Até pelo contrário, em concursos de programação eles dão-te sempre intervalos para trabalhar (raramente são superiores a 1.000.000) e o método do crivo demora menos de 1 segundo a calcular todos os primos nesse intervalo, e a memória ocupada não é por aí alem (1.90MB se usares um inteiro normal de C, 0.95MB um short int, 0.12MB se usares booleans (C++/Pascal). Qualquer dos valores é aceitável para um concurso.

Se fores pelo método "normal", aí sim, tás com problemas devido ao tempo de execução.

Obtens um "Runtime Error"

[mogers]

Até pelo contrário, em concursos de programação eles dão-te sempre intervalos para trabalhar (raramente são superiores a 1.000.000)

falaste bem ... "raramente" 👍 ... ja vi exercicios em k usar o crivo nao era viavel (pk os numeros eram bem maiores que 1M)... por acaso já foi há um tempo.. já não sei onde foi. cumps

[Warrior]

Mas se não usares um crivo (seja o de Erastótenes, seja o de Atkin (foi a primeira vez que ouvi falar)) o que usas? Não resolver não é uma opção.

[Triton]

Se alguém descobrir um exemplo do Crivo de Atkin em funcionamento era fixe!  👍

[saramgsilva]

Se alguém descobrir um exemplo do Crivo de Atkin em funcionamento era fixe!  😛

ya vou pesquisar sobre isso... não conhecia  😉

[José Oliveira]

Mais um exemplo: http://www.win.tue.nl/~ida/demo/c1s4ja.html

[Gurzi]

Bem, ontem decidi brincar com isto e pus-me a aprender java os básicos aplicando este conceito..

Gostava que analizassem o código e verificassem se existia alguma forma de melhorar ou incrementar a perfomance do programa..

class Primes{

  int[] primos;
  
  public Primes(int quantidade)
  {
  primos =  new int[quantidade];
  }

  public void isPrime(int[] numeros)
{
        
   // using Sieve of Eratosthenes
    
    for(int i = 2; i < (numeros.length / 2 ); i++)
    {
        for(int y = 1; y < numeros.length; y++)
        {
            if( numeros[y] % i == 0 && numeros[y] != i)
            {
                numeros[y] = 0;
            }
        }
    }
    
    showPrimes(numeros);
    }

public void start(int maxNumber)
{
    for(int i = 0,k= 2;i < maxNumber-1; i++,k++)
    {
        this.primos[i] = k;
    }
    isPrime(this.primos);
    
   
}


public void showPrimes(int[] value)
{
    for(int j = 0; j < value.length ; j++)
    {   
        if(value[j] != 0)
            System.out.println("Numero Primo : " + value[j] + "\n");
    }
}


public static void main(String[] args)
{
    Primes Pi =  new Primes(150);
    
    Pi.start(150);
    
  
}
}

Algumas dúvidas que podem surgir, inicei a 2 porque sei que o primeiro  numero primo é 2( o 1  não é porque é necessário 4 divisores inteiros) e iniciei o for do array na posição 1 porque o 0 é do 2..

Uma coisa que me fez confusão foi a ordenação do vector, gostava que me esclarecessem se é melhor fazer como fiz, ou seja, colocar 0 onde não são numeros primos, ou apagar os 0 e deixar o arrray só com os numeros primos..

Abraços

[Warrior]

Podes avançar o ciclo do y de i em i, e podes inicia-lo em i*i (desta forma também removes o if, pois todos os números onde ele calha são números para remover).

O i não precisa de ir até ao numeros/2, basta-lhe ir até à raiz quadrado do numeros.length.

Só entras no ciclo j, se o número i for primo (podes verificar no vector), caso contrário é desnecessário pois os números já foram todos cortados anteriormente.

Isto para um crivo "normal", é o que se costuma fazer.

Já vais ter um aumento de velocidade enorme se fizeres isto.

Se quiseres mais melhorias.. Podes primeiro remover os pares, e depois avançar o i de 2 em 2, pois não vale a pena verificar todos os outros.

Ou então repara que todos os primos são da forma 6k-1 ou 6k+1 (tirando o 2 e o 3), podes testar só esses..

[JC1]

Utilizar um bit para cada número, em vez de um byte.

[shumy]

Trabalha ao contrario. Uma versão desse algoritmo.

E usa listas não arrays.

Ao contrário é:

Começas com uma lista vazia (melhor logo com o 2), e um contador a 3.

Vaz incrementando o contador e dividindo por todos os elementos da lista, se é primo não é divisivel por nenhum da lista, então inseres na lista. Chegas ao fim com a lista de números primos e não gastas memória desnecessária.

Basicamente esqueci dizer que isto se apoia no metodo de factorização aprendido no ciclo.

Porque todos os números não primos são uma multiplicação de um conjunto de números primos.

[Warrior]

Esse método é mais lento, e não recorre ao crivo de Eratóstenes (o que ele pretendia inicialmente)

[djthyrax]

Se alguém descobrir um exemplo do Crivo de Atkin em funcionamento era fixe!  👍

C: http://cr.yp.to/primegen.html

Python: http://krenzel.info/?p=83

[Triton]

Se alguém descobrir um exemplo do Crivo de Atkin em funcionamento era fixe!  👍

C: http://cr.yp.to/primegen.html

Python: http://krenzel.info/?p=83

Por acaso já tinha visto hoje, fui ao site da Wikipedia e reparei... mas obrigado na mesma. 😉

[djthyrax]

Se alguém descobrir um exemplo do Crivo de Atkin em funcionamento era fixe!  👍

C: http://cr.yp.to/primegen.html

Python: http://krenzel.info/?p=83

Por acaso já tinha visto hoje, fui ao site da Wikipedia e reparei... mas obrigado na mesma. 😉

Foi onde eu vi também 😉