Ir ao conteúdo
  • Comunicados

    • Gabriel Torres

      Seja um moderador do Clube do Hardware!   12-02-2016

      Prezados membros do Clube do Hardware, Está aberto o processo de seleção de novos moderadores para diversos setores ou áreas do Clube do Hardware. Os requisitos são:   Pelo menos 500 posts e um ano de cadastro; Boa frequência de participação; Ser respeitoso, cordial e educado com os demais membros; Ter bom nível de português; Ter razoável conhecimento da área em que pretende atuar; Saber trabalhar em equipe (com os moderadores, coordenadores e administradores).   Os interessados deverão enviar uma mensagem privada para o usuário @Equipe Clube do Hardware com o título "Candidato a moderador". A mensagem deverá conter respostas às perguntas abaixo:   Qual o seu nome completo? Qual sua data de nascimento? Qual sua formação/profissão? Já atuou como moderador em algo outro fórum, se sim, qual? De forma sucinta, explique o porquê de querer ser moderador do fórum e conte-nos um pouco sobre você.   OBS: Não se trata de função remunerada. Todos que fazem parte do staff são voluntários.
    • DiF

      Poste seus códigos corretamente!   21-05-2016

      Prezados membros do Fórum do Clube do Hardware, O Fórum oferece um recurso chamado CODE, onde o ícone no painel do editor é  <>     O uso deste recurso é  imprescindível para uma melhor leitura, manter a organização, diferenciar de texto comum e principalmente evitar que os compiladores e IDEs acusem erro ao colar um código copiado daqui. Portanto convido-lhes para ler as instruções de como usar este recurso CODE neste tópico:  
Entre para seguir isso  
zarpon

Algoritmo Rápido Para Calcular Numeros Primos

Recommended Posts

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;

Compartilhar este post


Link para o post
Compartilhar em outros sites

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.

Compartilhar este post


Link para o post
Compartilhar em outros sites
  • Autor do tópico
  • 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.... :wacko:

    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;

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites

    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

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites
  • Autor do tópico
  • 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.

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites

    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..... :wacko:

    Espero ter ajudado...

    Rodrigo.

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites
    Guest thyagopolaco

    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

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites

    Crie uma conta ou entre para comentar

    Você precisar ser um membro para fazer um comentário

    Entre para seguir isso  





    Sobre o Clube do Hardware

    No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

    Direitos autorais

    Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

    ×