• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

saramgsilva

[Tutorial] O que é o Crivo de Eratosthenes?

69 mensagens neste tópico

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]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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  :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

Hei de tentar implementá-lo e comparar tempos... :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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"

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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" :thumbsup: ... 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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

ya vou pesquisar sobre isso... não conhecia  ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

preciso de umas explicações básicas..

Primeiro, porque fazer a raiz quadrada do máximo em vez de metade do maximo utilizado ?

Segundo, como uso um bit em vez de um byte ? ( nao percebi )

Terceiro, qual é a syntax de uma lista ao contrário de um array ??

Obrigado

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não programo JAVA, portanto só te posso responder a uma dessas perguntas.

Repara que um número "c" não é primo se existirem dois números a e b tais que "a x b = c". Na pior das hipóteses, a=b, logo basta pesquisar até à raiz quadrada.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

no algoritmo que uso, só faço modulo do numero pelos primos já descobertos cujo quadrado seja inferior ao numero, ou seja, para o numero 37, por exemplo, só faço 37%3 e 37%5, efectuando só duas operações...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora