Crivo de Eratóstenes

Embora não exista uma regra para descobrir todos os primos, é possível encontrar todos os primos menores que um dado número. Uma maneira de encontrar é através de um processo chamado de crivo que elimina sistematicamente os números compostos deixando passar pelo crivo apenas os números primos. Vamos apresentar o crivo desenvolvido por Eratóstenes (200 A.C), o terceiro bibliotecário-chefe da Biblioteca de Alexandria. 

Vamos aplicar o crivo de Eratóstenes para encontrar todos os números primos menores que 10.

Inicialmente, vamos considerar que todos os números de 2 até 10 são primos:
2 3 4 5 6 7 8 9 10

A cor preta representa os números não marcados. A cor vermelha representa os números eliminados. A cor azul representa os números que passaram pelo crivo, ou seja, os números primos. O primeiro número não marcado recebe a cor azul e todos os seus múltiplos recebem a cor vermelha.
2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10

Algumas modificações simples podem ser realizadas no algoritmo para tornar o algoritmo executa menos operações:

1. Inicialmente, vamos considerar que todos os números no intervalo são primos.
2. Elimine os múltiplos do número p que passou pelo crivo a partir de p*p.
3. Faça o crivo até 

 

Simulação do Crivo de Eratóstenes

http://www.cut-the-knot.org/Curriculum/Arithmetic/Eratosthenes.shtml

Código em C

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

#define MAX 1000001
#define NUM 78498 
 
int main(){
  int i,j;
  int limite;
  char ehprimo[MAX];
  int cont=0;
  int primos[NUM];
  FILE *fp;
  fp = fopen("primos.txt","wt");

  for(i=2;i<MAX;i++) ehprimo[i]=1;
  limite = (int)sqrt(MAX);
  for(i=2;i<limite;i++){
    if(ehprimo[i]){
      for(j=i*i;j<MAX;j=j+i)
        ehprimo[j] = 0;
    }
  }

  for(i=2;i<MAX;i++){
    if(ehprimo[i]){
      fprintf(fp,"%d %d\n",cont,i);
      primos[cont]=i;
      cont++;
    }
  }
  printf("%d\n",cont);   
  system("PAUSE");

}

Esse programa gera um arquivo contendo todos os números primos menores que 1000000.

Código C++

#include <iostream>
#include <fstream>
#include <bitset> 
#include <vector>
#include <cmath>
#include <cstdlib>
#define MAX 1000001

using namespace std;

int main(){

  bitset<MAX> bs; //vetor de bits
  vector <int> primos; //vetor de primos
  int limite;
  ofstream outfile ("primos2.txt");

  bs.reset(); //seta todos os numeros para 0 
  bs.flip();  //seta todos os numeros para 1
  
  cout << "Inicio do Crivo" << endl;
  limite = (int)sqrt(MAX);

  for (int i = 2; i <= limite; i++){ 
    if (bs.test((size_t)i)) {
      for (int j = i * i; j < MAX; j += i) 
        bs.set((size_t)j, false); 
    }
  }
  
  for(int i=2; i< MAX; i++)
    if (bs.test((size_t)i)){
      outfile << i << endl;
      primos.push_back(i);
    } 
  system("PAUSE");
}