Algoritmos Computacionais

Encontrar números primos é um problema comum em olimpíadas e maratonas de programação. Até hoje não existe uma maneira fácil de determinar se um número é ou não primo, mas para resolver estes problemas é indispensável o conhecimento de alguns algoritmos clássicos e simples, como o Crivo de Eratóstenes.

O Crivo de Eratóstenes é um método bastante prático para encontrar os primos de 2 até um valor limite, que pode ser feito a mão e é fácil de implementar.

O algoritmo consiste em:

1. Determinar (ou receber na entrada do programa) o valor limite, isto é, o maior número que desejamos saber se é primo.
2. Fazer a raiz quadrada do valor limite. Pode-se arredondar para baixo caso a raiz não seja exata (e quase nunca é).
3. Criar um vetor (lista) com os números de 2 até o valor limite.
4. Para i=2 até raiz do valor limite, caso o número (i) não esteja riscado insira-o na lista dos primos (ou imprima-o, ou não faça nada, isso depende da utilidade que você quer dar para o crivo) e risque todos os seus múltiplos na lista.

Há várias maneiras de implementar este algoritmo. Eu pseudocodaria (meu pseudocódigo é bem próximo de uma linguagem normal, porque acho que assim é mais fácil de entender e depois implementar) ele assim:

/* Primeiro passo */
recebe valorLimite

/* Segundo passo */
raiz  

/* Terceiro passo */
para i  2 até valorLimite
    vetor[i]  i
fim-para

/* Quarto passo */
para i  2 até raiz
    se vetor[i] = i
        imprima "O número " i " é primo."
        para j  i+i até valorLimite, de i e i
            vetor[j]  0
        fim-para
    fim-se
fim-para

Vêem como é simples?

Crivo de Eratóstenes implementado em C

#include <stdio.h>#include <math.h> // necessário para raiz #define NMAX 1000000 // valor máximo para o valor máximo int main() {    int i, j, vetor[NMAX];    int valorMaximo, raiz;     // Primeiro passo    scanf("%d", &valorMaximo);     // Segundo passo    raiz=sqrt(valorMaximo);     // Terceiro passo    for (i=2; i<=valorMaximo; i++) {        vetor[i]=i;    }     // Quarto passo    for (i=2; i<=raiz; i++) {        if (vetor[i]==i) {            printf("%d é primo!n", i);            for (j=i+i; j<=valorMaximo; j+=i) {                vetor[j]=0; // removendo da lista            }        }    }     return 0;}

No USACO Training Program Gateway (programa de treinamento para olimpíadas dos estado-unidenses) há um problema muito interessante (Prime Palindromes) cujo objetivo é determinar palíndromos primos de X a Y. Uma das melhores situações que já encontrei para usar o Crivo e sem dúvidas é um ótimo treinamento. Além de determinar primos, você terá que determinar palíndromos e é outro ótimo exercício lógico-matemático.

Divirtam-se e qualquer dúvida usem os comentários!