Re: Programa_para_achar_nºs_primos_...

["Franklin de Lima Marquezino" <fmarquezino@xxxxxxxxxx>]

    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 <ra992559@ic.unicamp.br>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Terça-feira, 4 de Dezembro de 2001 15:40
Assunto: Re: Programa_para_achar_nºs_primos_...


>--- Eleu Lima Natalli <eleu.vix@zaz.com.br> 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