Re: [obm-l] Como verificar a Primalidade?

["Henrique Rennó" <henrique.renno@xxxxxxxxx>]

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
=========================================================================