Eleu, se vc tiver Maple, existe um comando (isprime, s� n�o me lembro da
sintaxe, mas o comando � esse) que verifica se o n�mero � primo ou n�o,
usando um algoritmo probabil�stico, conforme j� foi explicado pelo Vinicius.
Vai a� um exemplo teste de primalidade probabil�stico, lembrando que o
algoritmo deve ser repetido para aumentar a probabilidade da resposta estar
correta:
input: n pertencente aos naturais >= 2
output: "composto" ou "possivelmente primo"
1- Se o �ltimo d�gito for 0, 2, 4, 5, 6 ou 8 ent�o retorne "composto"
2- Escolha "a" pertencente a {2, 3, 4, ..., n-2} uniformemente
randomicamente
3- b:= a^{n-1} rem n , onde rem significa remainder, resto da divis�o
4- se b=1 entao
retorne "possivelmente primo"
senao
retorne "composto"
fim-se
O m�todo mostrado pela Juliana alguns dias atr�s (faz tempo que eu n�o
confiro a lista :-)) � chamado de Crivo de Erast�tenes... tem alguma coisa
sobre isso no meu livro de Java. Ele � interessante, mas quando se trata de
n�meros muito grandes ele n�o � eficiente.
Um outro algoritmo que tamb�m poderia ser usado, seria dividir o n�mero
n por todos os n�meros de 1 at� sqrt(n). N seria primo se n�o fosse
divis�vel por nenhum deles. Tamb�m cai no mesmo problema do anterior. Ele
torna-se invi�vel quando o n�mero � muito grande.
Os mais usados mesmo, na pr�tica, s�o os algoritmos probabilisticos, que
retornam "composto" ou "provavelmente primo".
At� mais,
Franklin
"because nature isn't classical..."
(Richard P. Feynman - Computa��o Qu�ntica)
-----Mensagem original-----
De: Vinicius Jos� Fortuna <[EMAIL PROTECTED]>
Para: [EMAIL PROTECTED] <[EMAIL PROTECTED]>
Data: Ter�a-feira, 4 de Dezembro de 2001 15:40
Assunto: Re: Programa_para_achar_n�s_primos_...
>--- Eleu Lima Natalli <[EMAIL PROTECTED]> escreveu:
>> Alguem sabe em q site posso baixar o prog q ''ca�a''
>> n� primos ?
>
>O n�mero de primos at� n, para n grande, � em torno de n/ln(n).
>Ent�o temos que a probabilidade de um n�mero x ser primo � em torno de
>1/ln(x).
>
>Ent�o, se queremos um n�mero primo com o tamanho de n, teremos que
>procurar, em m�dia, aproximadamente ln(n) n�meros aleat�rios em torno de
>n para encontrar um que seja primo.
>
>Para cada um dos n�meros gerados, deve-se testar se ele � primo ou n�o.
>Normalmente faz-se isso com testes de pseudo-primalidade. Se o algoritmo
>retorna "composto" ent�o ele � definitivamente composto. Se ele retorna
>"primo" ent�o h� uma alta probabilidade de ele ser primos. A vantagem
>desses algoritmos � que eles s�o r�pidos o suficiente. Al�m disso, h�
>algoritmos que vc pode repetir v�rias vezes de forma que a chance de um
>erro de primalidade seja menor do que um erro de hardware!
>Um desses algoritmos � o de Miller-Rabin.
>At� mais
>
>Vinicius Fortuna
