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

Fatoração em primos

O resultado mais importante sobre os números primos é o chamado Teorema Fundamental da Aritmética que garante que todo número maior que 1 pode ser decomposto em fatores primos. Vamos apresentar o algoritmo que executa mais operações, mas que é mais fácil de ser entendido. O algoritmo consiste em testar os números menores ou iguais   e ir dividindo a medida do possível:

#include <stdio.h>
#include <math.h>
#include <vector>
#include <iostream>
#include <stdlib.h>
using namespace std;

vector <int> fatora(int n){
  int i,limite;
  vector <int> primos;
  i=2;
  limite = (int)sqrt(n);
  while(n > 1 && i<=limite){
    //se i divide n entao i eh primo retira todos os fatores i de n
    while(n%i==0){
      primos.push_back(i);
      n=n/i;
    }
    i=i+1;
  }
  //se i >= raiz de n entao n eh primo
  if(n>1)
    primos.push_back(n);
  return primos;
}

int main(){
  vector <int> primos;
  primos = fatora(120);
  printf("%d",primos[0]);
  for(int i=0;i<primos.size();i++)
    printf("*%d",primos[i]);
  printf("\n");
  system("PAUSE");
} 

SAÍDA 

2*2*2*2*3*5
Pressione qualquer tecla para continuar. . .

Podemos provar que nenhum número composto será adicionado no vetor primos.

Teorema: O algoritmo fatora encontra a decomposição em fatores primos.

Prova: Suponha por absurdo que um número não-primo foi adicionado no vetor primos (vetor que guarda a decomposição em fatores primos). Seja d o menor número não-primo adicionado no vetor primos. Pelo Teorema Fundamental da Aritmética, d também pode ser decomposto em fatores primos. Considere a seguinte decomposição de d = p_1*p_2*..._*p_k onde p_i < d. Logo, existe um primo p_i que foi “pulado” durante o algoritmo uma vez que p_i < d. Absurdo, todos os números menores que d são testados antes de d.  

O pior caso desse algoritmo tem a seguinte complexidade:

A segurança do sistema RSA depende da dificuldade da fatoração de um número n em fatores primos. Vamos imaginar que queiramos quebrar a criptografia de um sistema RSA com uma chave de 1024 bits. Logo, n ~ 2¹⁰²⁴ ~ 2¹⁰⁰⁰~ (2¹⁰)¹⁰⁰ ~ (10³)¹⁰⁰~ 10³⁰⁰. Precisamos testar aproximadamente ~10¹⁵⁰ números. Considerando que seja possível testar 10⁹ fatores por segundo. Para testar todos os valores possíveis ~10¹⁴¹ segundos ~ 10¹³⁰ milênios.  
 

Programa em JavaScript que descobre a decomposição em fatores primos utilizando esse algoritmo

Teste de Primalidade

Na escola, aprendemos que os números primos são especiais: ele tem exatamente dois divisores 1 e n e todo número maior que 1 pode ser representado de maneira única por produto de números primos (chamado de fatores primos). Este resultado é conhecido como Teorema Fundamental da Aritmética. 

Na Grécia Antiga, Euclides já tinha percebido que os primos eram os blocos fundamentais, os átomos, que constituem o edifício dos números inteiros. Vários matemáticos tentaram encontrar uma fórmula para descobrir os primos, mas, até agora, nenhum matemático conseguiu a solução desse antigo quebra-cabeça. 

Euclides (300 AC) formulou e respondeu a seguinte pergunta sobre os primos:

Os números primos são finitos ou infinitos?

Para responder esta pergunta, ele utilizou um método de prova chamada redução ao absurdo.

Prova: Suponha por absurdo que a quantidade de números primos é finita e pode ser listada da seguinte maneira P = {p1,...,pk}. Seja N definido como o produto de todos os primos somando mais 1:

N = p1*...*pk + 1

Nenhum primo pode ser divisor de N, pois para todo pi, N % pi = 1. Como nenhum primo é divisor de N então N não pode ser dividido por nenhum primo. Portanto, N é também um número primo,  mas  N não pertence ao conjunto P. Absurdo!

Até onde eu preciso testar para saber se um número é primo ou não?

Se n não é primo, então o menor divisor de n, d_0, menor ou igual a .

Este resultado também pode provar utilizando a redução por absurdo.

Prova: Suponha por absurdo que n não é primo e o menor divisor de n d₀ maior que  .

d₀ > 

d₀² > n

d₀ > n/d₀

Temos que d₀ é um divisor (e fator primo) de n e podemos escrever n = d₀*k onde k  Z. Temos também n/d₀ é um divisor de n, uma vez que, podemos escrever n = (n/d₀)*d₀  e d₀  Z.

Absurdo, d₀ é o menor divisor de n e existe um outro divisor de n, n/d_0, menor que d_0.

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

/*
funcao ehprimo(n) retorna 0, se n nao eh primo 
                          1, se n eh primo

se i eh divisor de n entao n nao eh primo

se nenhum numero 2<=i<=sqrt(n) eh divisor de n entao n eh primo 
*/
int ehprimo(int n){
  int limite;
  limite = (int)sqrt(n);
  for(int i=2;i<=limite;i++){
    if(n%i==0) return 0;
  }
  return 1;
}

int main(){
  int cont=0;  
  for(int i=2;i<=1000000;i++){
    if(ehprimo(i)) { 
      cont++;
    }

  }
  printf("numeros primos menores que 1000000: %d\n",cont);
  system("PAUSE");

}

Saída
numeros primos menores que 1000000: 78498
Pressione qualquer tecla para continuar. . .

Podemos conferir o resultado aqui:
http://www.wolframalpha.com/input/?i=number+of+prime+from+1+to+1000000


Gauss tentou responder uma pergunta interessante sobre os números primos:
Quantos primos existem até um certo número n?
Gauss era fascinado por um suplemento do seu livro de logaritmos que trazia uma tabela de números primos. Os logaritmos eram previsíveis mas os primos eram completamente aleatórios. Parecia não existir qualquer conexão entre os logaritmos e os primos. Gauss denotou a quantidade de números primos até x e observou essa estranha relação entre e log(x).



A fórmula que ele encontrou é uma boa aproximação para a quantidade de  números de primos até um certo número.

Confira aqui:
Comparação até 100
Comparação até 1000
Comparação até 10000
Comparação até 100000
Comparação até 1000000

Links relacionados:
http://elementosdeteixeira.blogspot.com/2012/02/o-desafio-dos-numeros-primos.html