Meu irmão ( esse e-mail é dele e ele me deixa usar para tirar minhas dúvidas) um dia me falou, se não estou engando, que para os números primos temos dois tipos de verificação: Determinística e probabilística. Pelo que pude entender, posso dizer que o Crivo de Eratóstenes é determinístico e o pequeno teorema de Fermat probabilístico? Alguém poderia me listar quais são os métodos determinísticos e quais são os probabilísticos?
Obrigado pela força Herique Rennó.
Obrigado
Lincoln
From: "Henrique Rennó" <henrique.renno@gmail.com>
Reply-To: obm-l@mat.puc-rio.br
To: obm-l@mat.puc-rio.br
Subject: Re: [obm-l] Como verificar a Primalidade?
Date: Thu, 6 Apr 2006 22:18:26 -0300
>Olá Rhilbert e pessoal da lista!!!
>
>Devem existir outros métodos mais avançados para verificar se um
>número é primo ou não. Eu usualmente resolvo problemas de programação
>em sites de maratonas de programação online, e quando é necessário
>utilizar uma função que verifique se um número N é primo, a forma mais
>eficiente é verificar se ele é par, e caso não seja, verificar se ele
>é divisível por todos os números ímpares a partir do 3 até que o
>índice do laço seja maior que a raiz quadrada do número N, ou seja,
>praticamente o método que você descreveu.
>
>Os números primos possuem muitas fontes de pesquisa na Internet e
>existem alguns livros sobre eles e problemas relacionados, como a
>Hipótese de Riemann. Um dos livros que tenho em pdf é o "Prime
>Obsession" do autor John Derbyshire que achei no emule. É um excelente
>livro para quem quer entender a problemática dos números primos e
>sobre a matemática avançada que leva à Hipótese de Riemann, assim como
>qual seria o impacto de uma possível solução ou não solução da
>hipótese.
>
>Um livro legal, mas para leigos, sem muita matemática, é o "Problemas
>do Milênio" do autor Keith Devlin que o escreveu após conversa com um
>pessoal do CMI (Clay Mathematics Institute - www.claymath.org). Esse
>livro é uma grande fonte de informações sobre quais as idéias que
>estão por trás de cada problema.
>
>Caso você veja algum método sobre verificação de números primos que
>seja complicado poste aqui na lista, pois tenho certeza que o pessoal
>vai ajudar bastante (eu também vou tentar).
>
>Abraços!!!
>
>On 4/6/06, Rhilbert Rivera <rhilbert1990@hotmail.com> wrote:
> >
> >
> >
> >
> > Pessoal, me ajudem a superar uma deficiência.
> >
> > Se eu quisesse saber se 97 é um número primo, extrairia o piso da raiz
> > quadrada de 97 e dividiria 97 pelos primos menores ou iguais ao valor do
> > Piso. Como 97 não seria divisível por nenhum desses primos, logo ele é um
> > número primo. Tendo um trabalhão eu faria a mesma coisa para 17443, e ainda
> > teria o problema de saber quais são todos os primos menores ou iguais que o
> > Piso da raiz quadrada de 17443!!!!!
> >
> > Minha pergunta é: Para números não tão grandes, de que outras maneiras eu
> > poderia fazer essa verificação? Quantas maneiras existem para fazer isso?
> > Elas são tão difíceis que é melhor continuar só com essa?
> >
> > Agradeço as respostas e a parti delas vou procurar estudar mais.
> >
> > Obrigado
> > ________________________________
> > Inscreva-se no programa beta do novo Windows Live Mail e seja um dos
> > primeiros a testar as novidades. Saiba mais: Saiba mais!
> > =========================================================================
> > Instruções para entrar na lista, sair da lista e usar a lista em
> > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> > =========================================================================
>
>
>--
>Henrique
>"Não há ninguém que seja tão grande que não possa aprender e nem tão
>pequeno que não possa ensinar."
>"There's no one that is so great that could not learn nor so small
>that could not teach."
>"O indivíduo confiante tenta mais, erra mais, aprende mais." - Piaget
>"The confident individual try more, err more, learn more." - Piaget
>
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>=========================================================================