Algoritmo Rápido Para Calcular Numeros Primos

[zarpon]

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:

procedure divide;

begin

s1:= k mod 2;

if s1<>0 then

begin

s2:= k mod 3;

end;

if s2<>0 then

begin

s3:= k mod 5;

end;

if s3<>0 then

begin

s4:= k mod 7;

end;

end;

if (s1<>0) and (s2<>0) and(s3<>0) and(s4<>0) then

begin

y:=k;

for z:=k downto 8 do

begin

resp:= y mod z ;

if resp=0 then

begin

cont:=cont+1;

end;

if (cont>1) then

break;

end;

if cont=1 then

begin

write(y,' ');

cont2:=cont2+1;

write(arq,y,' ');

end;

cont:=0;

end; //fim se divide;

[romudd]

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.

Por exemplo:

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.

[zarpon]

Postado Originalmente por romudd@27 de setembro de 2005, 12:09

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.

Por exemplo:

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.

←

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

begin

resp:= y mod z ;

if resp=0 then

begin

cont:=cont+1;

end;

[romudd]

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

exemplo:

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

[zarpon]

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.

obrigado.

[romudd]

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:

50 x 2 = 100

20 x 5 = 100

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!

ufa.....

Espero ter ajudado...

Rodrigo.

[Visitante]

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).

espero que ajude....se isso resolve o caso me comunique....falou

[De Los Santos]

Não sei se vai te ajudar, mas nesse tópico foi falado sobre a mesma coisa:

http://forum.clubedohardware.com.br/index....howtopic=200180