Crivo de Eratóstenes Simples em C

Publicado por Perfil removido (última atualização em 14/05/2012)

[ Hits: 9.803 ]

Download sieve001.c




Crivo simples. Valores devem ser ajustados.

Obs[1]: Dependendo do compilador, sistema ou memória disponível, corrigir para não haver overflows.
Obs[2]: O tamanho do crivo pode ser calculado exato e quase exato, dependendo do limite colocado.
Obs[3]: Quem puder testar e fazer "benchmark" com valores elevados e sistemas mínimos, máquinas virtuais etc. eu agradeceria.

  



Esconder código-fonte

#include <stdio.h>
#include <math.h>

typedef unsigned long long llint;


int main (void) {

   const llint p = (llint) (pow (2.0, 23.0) -1.0);
   const llint q = 1009999; // (llint) (2.0 * ((double) p / log((double) p)));

   llint primes[q];

   llint i=5, j=0, k=0, l=1, m=0;

   for (m=0; m<q; m++) primes[m]=1;

   primes[0]=2;
   primes[1]=3;

   do {

      j = 0;
      k= (llint) sqrt((double) i);

      while ((primes[++j]<k) && (i%primes[j]));

      if (primes[j]>k) primes[++l] = i;

      i+=((i%3==2)?2:4);

   } while (i<p && l<q);

   for (m=0; m<l; m++) printf ("%llu ",primes[m]);
   putc ('\n',stdout);

   return 0;

}

Scripts recomendados

Calcular a potência de um número.

Inserir e remover caracter da matriz

A máquina nao perdoa (jogo da velha em c -arquivo correto, agora)

Algoritimo pra Multiplicação de Matrizes

Sopa de Letras


  

Comentários
[1] Comentário enviado por removido em 17/04/2012 - 08:42h

A exemplo de outro código, por este também usar a função de raiz quadrada - sqrt() - também deve se compilado com a opção "-lm":

gcc sieve001.c -o sieve001 -lm

[2] Comentário enviado por removido em 04/05/2012 - 17:23h

# time ./sieve001 > /dev/null

real 0m2.652s
user 0m2.639s
sys 0m0.002s


vendor_id : GenuineIntel
cpu family : 6
model : 42
model name : Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
stepping : 7
microcode : 0x25
cpu MHz : 1600.000
cache size : 8192 KB

MemTotal: 3872260 kB



Linux version 3.3.2-6.fc16.x86_64 ([email protected]) (gcc version 4.6.3 20120306 (Red Hat 4.6.3-2) (GCC) ) #1 SMP Sat Apr 21 12:43:20 UTC 2012

[3] Comentário enviado por removido em 04/05/2012 - 17:56h

Comentário enviado por dstanzani em 04/05/2012 - 17:23h:

# time ./sieve001 > /dev/null

real 0m2.652s
user 0m2.639s
sys 0m0.002s


vendor_id : GenuineIntel
cpu family : 6
model : 42
model name : Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
stepping : 7
microcode : 0x25
cpu MHz : 1600.000
cache size : 8192 KB

MemTotal: 3872260 kB



Linux version 3.3.2-6.fc16.x86_64 ([email protected]) (gcc version 4.6.3 20120306 (Red Hat 4.6.3-2) (GCC) ) #1 SMP Sat Apr 21 12:43:20 UTC 2012


Valeu! Mas esse programa está com uma lamentátel erro e eu já enviei a correção. Vale a pena diminuir o valor de p prá < 1000, que é nessa faixa menor que se identifica visualmente o erro.

Eu devo ter enviado uma versão de teste por engano. ><

[4] Comentário enviado por removido em 14/05/2012 - 13:57h

*** ATENÇÃO ***

O programa que está aparecendo integralmente no browser *** NÃO É O PROGRAMA CORRIGIDO ***.

Quem se propuser a executá-lo deverá baixar o sieve001a.c que é diferente do sieve001.c.


[6] Comentário enviado por paulo1205 em 21/06/2016 - 13:09h

O algoritmo mostrado NÃO CORRESPONDE ao Crivo de Eratóstenes. O Crivo de Eratóstenes não usa divisão (ou módulo, que dá na mesma), nem precisa calcular raiz quadrada.

Eis o verdadeiro crivo de Eratóstenes (em C++-like não otimizado).

std::vector<bool> is_prime(N_MAX+1, true);
is_prime[0]=false;
is_prime[1]=false;
unsigned n=2;
while(n*n<=N_MAX){
  for(unsigned k=n+n; k<=N_MAX; k+=n)
    is_prime[k]=false;
  do
    n++;
  while(!is_prime[n]);
}
// Neste ponto, todos os elementos de is_prime que tiverem valor true
// estarão em posições cujo índice é primo.



*EDIT*:
Eu falei que a versão acima não usa divisões. Não usa no crivo em si. mas o fato de eu ter usado std::vector<bool> pode implicar divisão.

Explico: para otimizar o uso de memória, os vários bits do vetor de booleanos (cada booleano é um bit) são agrupados em unidades de memória maiores (char ou int, dependendo da arquitetura), e o acesso ao elemento N de um std::vector<bool> pode acabar provocando o mapeamento do elemento (N/CHAR_BITS) de um vetor de caracteres, sobre o qual ainda se terá de fazer um e-lógico bit-a-bit para seleção do bit correto, com algo na forma (1<<(N%CHAR_BITS)).

Por outro lado, se CHAR_BITS for uma potência de 2, as operações de divisão e módulo pode ser parcialmente otimizadas com operações bit-a-bit, muito mais rápidas. Por exemplo, (N/CHAR_BITS) pode virar (N>>log2(CHAR_BITS)), e (N%CHAR_BITS) pode ser simplificado como (N&(CHAR_BITS-1)). Para o caso comum, principalmente nos nossos PCs, em que CHAR_BITS==8, o índice do vetor de caracteres é (N>>3) e a máscara para o bit é (1<<(N&7)).

Se o programa que eu mostrei acima for alterado para usar std::vector<char>, ele vai executar muito mais rapidamente, por eliminar as divisões e restos (ou deslocamentos para direita e para a esquerda e um e-lógico bit-a-bit) -- ao preço de usar possivelmente oito vezes mais memória.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts