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:
- Determinar (ou receber na entrada do programa) o valor limite, isto é, o maior número que desejamos saber se é primo.
- Fazer a raiz quadrada do valor limite. Pode-se arredondar para baixo caso a raiz não seja exata (e quase nunca é).
- Criar um vetor (lista) com os números de 2 até o valor limite.
- 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 \leftarrow \sqrt{valorLimite}
/* Terceiro passo */
para i \leftarrow 2 até valorLimite
vetor[i] \leftarrow i
fim-para
/* Quarto passo */
para i \leftarrow 2 até raiz
se vetor[i] = i
imprima "O número " i " é primo."
para j \leftarrow i+i até valorLimite, de i e i
vetor[j] \leftarrow 0
fim-para
fim-se
fim-paraVê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!
Comentários
Rafael Domingos
está errado o code em C…
Junio
Muito bom, bom mesmo.Muito obrigado pelo ensinamento, pois irá me ajudar bastante.Paz e saúde para ti.
mariano
parabens.. muito bom seu site estou adorando… semear conhecimento é a melhor forma de de semear igualdade… parabens
andre
eu sou o andre e vai po caralho
Gustavo Felisberto
Isto está mal. Como se pode facilmente verificar ao correr este algoritmo ele apenas testa até sqrt(MAX), se MAX for primo, não vai ser testado e não será indicado. QED. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Felipe Schneider
Acabei de ler :) Acho até que vou estudar e participar da Olimpíada nesse 2008!
Fabiano Lages Arouche
Bom… Primeiro gostaria de dizer que a questão matemática exposta aqui é citado no livro O Homem que Calculava de Júlio César de Melo e Sousa ( Malba Tahan )escritor, professor universitario e conhecedor da cultura Árabe. No Capítulo onde fala do “homem que não podia olhar para o céu”: Eratóstenes - filósofo grego. No livro é citado os cálculos do atrônomo, inclusive a descoberta da costelação de Sirius. Alfa do Cão Maior. nota do proprio autor.
ingrid morgana gomes paes
que bacana que legau isso e emtesamte e legau para apremder mais a matematica e buscar o que e eratotene vc que aimda nao conemseu o que e eratotenes connhesa e apramda mais matematica
Roger
Bom artigo. Podia atualizar esse site
NEZITA
bem….. n perSebo mt diSto xD MELHOR DISEMDO N PERSEBO ND LOOL MAS APRESIO_TE TIAGO MADEIRA TENS PAXSENSIA PA FAZER ISTO LOOL XD BJS
NEZITA
TENS PACIENCIA PA ISSO JA EU… LOOL XD BJS
Thalita
Perfeitooo!! Muito Obrigada!
José Sérgio
Olá, no comentário (4) o Gustavo afirma que há uma falha, já que o algoritmo faz o teste até a raiz quadrada de MAX. Na realidade não há problema algum com isso! Sou matemático e posso afirmar que para verificar se um número é primo, basta verificar se ele é ou não divisível por qualquer fator primo menor do que ou igual à sua raiz quadrada. Obviamente, se o número possuir raiz exata ele não é primo, portanto o problema é, como verificar até a raiz se ele pode não ser exata? Ora, basta tomar a parte inteira da raiz mais um. Ex: Se a raiz do número for 7,33, basta verificar se o número em questão não é divisível por nenhum primo até 7+1=8, ou seja, 2, 3, 5 e 7. Se ele não for divisível, podemos afirmar que o número é primo, caso contrário é um número composto. Valeu!
Leticia
Cara eu tenho 13 anos e estou começando a aprender isso mais é muito complicado!! :(
samela
é eu concordo com a leticia é muito complicado mesmo!! eu não entendi nadinha!! :(
janaina aparecida de souza
meu nome é janaina tenho 12 anos e adorei a esplicação apesar de ser muito dificil adorei miuto obrigada pela as esplicações beijos
Mateus
Algoritmo tranquilo. So que tem 2 problemas na implementacao em C: #1 - O vetor de tamanho “NMAX” (1000000) eh muito pra alocar na pilha, deve ser alocado via heap (malloc) #2 - O programa removeu os itens que nao sao primos, mas so imprime os primos ate a raiz do maximo. Um while() apos o for() fez o restante. Aqui esta o codigo alterado e compilando com gcc 4.4.0: ```
#include #include #include
int main(int ArgCount, char **ArgValue) {
int i, j, *vetor;
int valorMaximo, raiz;
}
Mateus
E para rodar: crivo.exe =]
Mateus
maldito html … pra rodar: crivo.exe “valor maximo”
Juliano
Excelente material. Parabens pelo Site! Atualize sempre que possível.
yasmim
Nossa…estou no 5° ano e estou aprendendo isso!!facil
cocozito
que porcaria de site meu…
Dionis
Tem umas retardada aqui que nem escreve nao sabem! Nezita e Ingrid sao as mesmas pessoas, ou sao duas que tem que voltar ao primario antes de siquer pensar em fazer programação! Ma va lava o cú com soda!
Sincero
Infelizmente isso parece ser contagioso… você escreve quase tão mal quanto elas! Não conhece infinitivo verbal e acabou de inventar uma nova palavra (siquer). Sem contar as demais asneiras…
Joquim Floriano de Souza
To tentando entender isso tudo pra poder auxiliar meu filho que faz ads, mas tá muito dificil,,,qual seria o melhor livro para comprar.
Tiago Madeira
Senhor, se quer mesmo auxiliar seu filho deixe-o em paz.
gui
engraçado essa galera que faz ADS, nego sabe fazer script de mirc e macro no word e acha que vai ser programador. ai fica se perdendo em crivo de eratostenes, quero ver entender p vs. np
cú preto
não gostei nada da resposta
cú preto
vcs não sabi esplicar
kah
haha…o cara ficou bravinho pk elas digitaram errado e fez isso tb… »siquer«
ilis
eu estou estudando isso i achei ñ muito complicado!
Marcelo
Eu estou estudando fundamentos de programação e tenho uma versão em Pascal que não acha raiz e não entendi como se processa em Pascal. Você conhece ou quer te envie, para poder me explicar? Obrig., Marcelo
vixi
assim nao pode…
Jakapa
Eu também estou a dar isso mas ainda não entendi algumas coisas! E por isso tenho muitas dúvidas! :( :)
Jcccp
Cara amiga é simples fazer isso, mas o segredo não digo! Boa sorte para vocês todos e continuem com dúvidas para ficarem melhores alunos! Porque se tiverem dúvidas e disserem ao vosso professor ele diz para toda a turma e por isso ele diz: Boa, continua a fazer essas dúvidas e compreenderás melhor as tuas dúvidas! É de facto um caso interessante resolver isso mas continuem! :) (O) (P) (C)
len
Tiago Madeira, seu link da USACO (com o interessante problema dos “números primos palíndromos”) está pedindo senha e login e isso certamente, quase nenhum dos usuários/visitantes deste seu blog de algoritmos aqui possui … De qualquer forma, como não desisto fácil da minha curiosidade, fuçando no google, consegui achar alguns problemas da mesma USACO sobre estes nr°s primos citados e os coloco aqui com os links de acesso [e sem pedir senha … affffff], mas com um porém: os textos estão inglês. http://hi.baidu.com/hycdqzc/blog/item/ea7c666245976649eaf8f868.html http://greenmoon55.com/usaco-prime-palindromes/ Enfim, espero ter ajudado a todos os curiosospelos nr°s primos … !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Adeus.
eu
ñ tendi nada!!! kkk
pamela
o seu site e muito mal cara fais outro pela mor em.
pamela
muito mallllllllllllllll
Jose Paulo
Isto é muito confuso e eu tenho um enigma e quero saber a resposta. Cá vai: Constrói um crivo de eratostenes com todos os números de 1 a 50, mas coloca na primeira linha menos de 10 números. Indentifica as principais diferenças entre este crivo e o crivo inicial.
Carolina
Thiago, Estou fazendo a disciplina Algoritmos no meu mestrado mas nao tenho muita base, ja q sou Matematica. Meu professor ensinou o crivo e disse que a complexidade é n vezes raiz de n. Para mim era apenas raiz de n. Por que multiplica por n? Obrigada.
Tiago Madeira
Oi Carol, você está certa. A complexidade é raiz de N, não N raiz de N.
vitoria
agora estou comecado a entender tem que tira todos os multiplos dos numeros na prova acho que vou acerta vou tira um 100
vitoria
vitopria disse apredi vou tira um dez na prova eu acho bjs
Crivo de Eratóstenes (números primos). | luisthiago
[…] Imagem retirada do http://tiagomadeira.com/2007/06/crivo-de-eratostenes/ […]
yohanna felix
Teria como passar para a linguagem javascript sem muita mudança ?