algoritmo: do Lat. algorithmos < Ár. alkharizmi: [Inform.] conjunto de etapas bem definidas necessárias para chegar à resolução de um problema.
June 17, 2007
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:
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?
#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!
Compare Preços de: notebooks, acer aspire, hp pavilion, computadores, pentium 4, nintendo wii, ps3, celulares, câmeras digitais
Este design foi copiado do CSS Zen Garden e modificado com autorização de seu autor, Gunta Klavina.
Todo o conteúdo deste site (incluindo textos, imagens, arquivos de áudio e quaisquer outros trabalhos), exceto quando especificado o contrário, está licenciado por Tiago Madeira sob uma Licença Creative Commons.