Algoritmo Rápido Para Calcular Numeros Primos - Programação - outros - Clube do Hardware
Algoritmo Rápido Para Calcular Numeros Primos
Por zarpon, 27 de setembro de 2005 em Programação - outros
aê pessoal...to com um trabalho da faculdade pra fazer e queria uma ajudinha do pessoal que entende de programação aqui do fórum.
É o seguinte, preciso criar um programa(pascal) pra calcular todos os numeros primos até um numero máximo que o usuario digita, ex: Se o usuario digita 1 milhão, o programa tem q mostrar todos os primos até 1 milhão.
Bom, eu criei o programa, mas com o algoritmo q to usando o calculo de numeros muito grandes demora muito, queria saber se alguém pode dar algumas dicas pra resolver isso.
To usando o seguinte algoritmo:
Pego o numero e divido por 2, 3, 5, 7
Se divide por algum deles não é primo.
Se não divide por nenhum deles então
o numero é divido por ele mesmo, um contador é incrementado.
Passa o loop e o numero é divido pelos antecessores dele, se encontrado outro divisor então não é primo e ele pula para o proximo numero.
Uns pedaços do fonte:
s1:= k mod 2;
s2:= k mod 3;
if s2<>0 then
s3:= k mod 5;
if s3<>0 then
s4:= k mod 7;
if (s1<>0) and (s2<>0) and(s3<>0) and(s4<>0) then
for z:=k downto 8 do
resp:= y mod z ;
if resp=0 then
if (cont>1) then
write(arq,y,' ');
end; //fim se divide;
Olha, assim de imediato eu não vejo uma forma diferente de chegar a essa lista do que testando os números um a um. No entanto, tem uma dica que vai ajudar a tornar mais rápido:
Quando estiver testando um número, você só precisa verificar até o último inteiro antes da raiz quadrada dele.
o número 103
raiz de 103 dá 10,14889......
Você só precisa ver se tem divisores até o 10. Se não tiver, não vai ter depois também. Então é primo.
Postado Originalmente por romudd@27 de setembro de 2005, 12:09
Rapaz é uma boa ideia...já economizava muito calculo...mas agora o problema é q não to sabendo fazer issow....
tipo....como eu converto o resultado dessa raiz encontrada sempre pra inteiro?...porque no loop não posso usar extended...tem q ser longint....
ai tipo pra dar certo assim:
obs:raiz (nome da variavel q recebe a raiz do numero)
for z:=k downto raiz do
Eu não conheço bem Pascal, mas a maioria das linguagens possui função matemática que arredonda números para inteiro. Dei uma olhadinha na internet, me parece que a função Round() faz isso
http://www.pascaltotal.hpg.ig.com.br/básico/exp_arit.htm
raiz_inteira := round(raiz)
Observei também uma coisa que pode ser um erro na implementação do algoritmo:
Você deve testar a divisão pelos números entre dois e a raiz quadrada. Se o número k tiver divisores, com certeza haverá algum deles dentro desse intervalo.
Pelo seu código, me parece que você está testando os números entre a raiz e o k.... é mais demorado, e talvez não seja 100% confiável
Dividindo o numero somente de 2 até a raiz dele ainda sim é possivel achar numeros q não são primos e q mesmo assim não dividam 2, 3, 5, 7 nem a raiz(arredondada) dele, pois acima dessa raiz ele ainda pode ter divisores.
mas sua dica já ajudou bastante porque agora meu loop só desce até o ultimo numero antes da raiz do numero.
Pode parecer esquisito à primeira vista, mas é verdade mesmo: se um número não é primo, PELO MENOS UM DE SEUS DIVISORES é menor ou igual à raiz quadrada.
Testando a divisão pelos números que estão entre 2 e a raiz, claro que você não vai obter a lista completa de divisores, mas se você achar só um é suficiente para determinar que o número não é primo. E se não achar nenhum divisor menor ou igual à raiz, com certeza não existe nenhum, ou seja, é primo.
Como o seu objetivo é melhorar a velocidade do programa, acho que você deveria pensar em adotar esse método, afinal existe menos números no intervalo 2-até-raiz do que no intervalo raiz-até-k
Para exemplificar, vamos tomar o numero 100
a raiz de 100 é igual a 10 pois 10x10=100
Temos os seguintes divisores menores que 10: 2 e 5
Existem divisores maiores que 10?
Claro que existem (20 e 50), mas veja:
Viu? Os divisores maiores que 10 existem, mas dependem dos menores (2 e 5) para que a multiplicação dê 100. Não tem como multiplicar dois numeros maiores que 10 e dar 100!!!!!
Conclusão: Se um número tem um divisor maior que sua raiz quadrada, OBRIGATORIAMENTE existe um outro divisor que é menor. Se você encontra-lo significa que o numero não é primo. Mas se não existir divisor menor que a raiz, Também não existirá o maior!
faz o seguinte: verifique se há divisores do número até a raiz inteira do numero que você quer verificar, se existe divisor então o resto da divisao é igual a zero. portanto verifique se a freqüência de restos zeros é maior do que dois, pois um número primo só divisivel por um e por ele mesmo....e se você não quiser verificar todos os numeros até a raiz de um número basta interromper o loop quando a freqüência de zeros for maior do que dois(2).