Jump to content

[Tutorial] O que é o Crivo de Eratosthenes?


saramgsilva
 Share

Recommended Posts

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:

algoritmo:crivo_de_eratosthenes.gif

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]

Link to comment
Share on other sites

  • Replies 68
  • Created
  • Last Reply

Top Posters In This Topic

  • Warrior

    15

  • mogers

    10

  • Triton

    5

  • skin

    5

Top Posters In This Topic

O algoritmo do Crivo de Eratosthenes

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

Cumpr. brink@ero  👍

Link to comment
Share on other sites

é 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).

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

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... :P

Link to comment
Share on other sites

é 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"

Link to comment
Share on other sites

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

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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..

Link to comment
Share on other sites

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.

Aqui há coisa de 2 anos fazia umas malhas de croché, depois fartei-me e fui para informática!

Link to comment
Share on other sites

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 ;)

Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.