Ah! Isso me lembra aquele metodo infalivel da programacao matematica para se mostrar que uma solucao eh otima. Baseia-se na definicao de solucao otima, segundo a qual uma solucao x* de um problema de maximizacao eh otima se tivermos f(x) <= f(x*) para todo x no conjunto viavel, sendo f a funcao objetivo. Ateh hoje, esta eh a unica condicao de otimalidade absolutamente geral que se conhece. Para mostramos que x* eh otima, basta mostramos que x* eh melhor ou tao boa quanto qualquer outra solucao.... Artur
--- Cláudio_(Prática) <[EMAIL PROTECTED]> wrote: > Tem um método que é infalível, apesar de ser também > totalmente inútil na > prática: veja se (n-1)! é divisível por n (supondo n > > 4). Se for, então n é > composto. Se não for, então n é primo. Isso é > consequência do teorema de > Wilson, que diz que n é primo se e somente se n > divide (n-1)! + 1. > > []s, > Claudio. > > ----- Original Message ----- > From: <[EMAIL PROTECTED]> > To: <[EMAIL PROTECTED]> > Sent: Friday, April 09, 2004 10:56 PM > Subject: Re: [obm-l] dúvida!!! > > > > > como eu posso saber de certeza que certo número > não primo? alguma idéia > > > brilhante senhores???? > > > [...] > > > > Se n é o tal número, calcule 2^(n-1) (mod n). Se o > resultado *não* der 1, > > você tem certeza absoluta de que o número é > composto. Por outro lado, se > > der um, você ainda não sabe nada. > > > > Se você ainda estiver desconfiado, você pode > tentar calcular 3^(n-1) (mod > > n) -- se der diferente de um, o número é composto. > Novamente, se a conta > > der um, isso não quer dizer nada. > > > > Você pode repetir isso quantas vezes você quiser, > desde que a base da > > potência não seja um múltiplo de n. A mesma coisa > vale: se der diferente > > de um, o número é composto, mas não vale a > recíproca. Por exemplo, 2^340 - > > 1 é divisível por 341 = 31*11. > > > > Pior, existem números, como o n = 561 = 51*11 tal > que, se mdc(a, n) = 1, > > então a^(n-1) - 1 é divisível por n. > > > > Se você quiser saber mais sobre números primos, o > livro "Primos de > > Mersenne (e outros primos muito grandes)" do > Nicolau e do Gugu, disponível > > em > > > > http://www.mat.puc-rio.br/~nicolau/publ/publ.html > > > > é um ótimo começo. > > > > []s, > > > > -- > > Fábio Dias Moreira > > > > > > > ========================================================================= > > 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 > > > ========================================================================= > > ========================================================================= > 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 > ========================================================================= __________________________________ Do you Yahoo!? Yahoo! Tax Center - File online by April 15th http://taxes.yahoo.com/filing.html ========================================================================= 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 =========================================================================