Crivo de Eratóstenes Simples em C [C/C++]

Crivo de Eratóstenes Simples em C

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

[ Hits: 10.361 ]

Download sieve001.c

1 1

Denuncie Favoritos Indicar

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

Verificador de senhas: comparando palavras

Antecessor e sucessor

Multiplicação de matrizes

Constantes de barra invertida

Ávores binárias em C

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

0 0

[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 (mockbuild@x86-06.phx2.fedoraproject.org) (gcc version 4.6.3 20120306 (Red Hat 4.6.3-2) (GCC) ) #1 SMP Sat Apr 21 12:43:20 UTC 2012

0 0

[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 (mockbuild@x86-06.phx2.fedoraproject.org) (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. ><

0 0

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

0 0

[5] Comentário enviado por removido em 20/02/2015 - 03:13h

http://www.vivaolinux.com.br/script/Crivo-de-Eratostenes-Simples-para-Linux-x86-em-Assembly-Puro-GNU...
http://www.vivaolinux.com.br/script/Crivo-de-Eratostenes-Simples-em-Fortran-95
http://www.vivaolinux.com.br/script/Crivo-de-Eratostenes-Simples-em-Pascal
http://www.vivaolinux.com.br/script/Crivo-de-Eratostenes-Simples-em-Perl
http://www.vivaolinux.com.br/script/Crivo-de-Eratostenes-Simples-em-PHP
http://www.vivaolinux.com.br/script/Crivo-de-Eratostenes-Simples-em-Ruby

--
Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden

0 0

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

0 0