Re: Programa_para_achar_nºs_primos_...

[Vinicius José Fortuna <ra992559@xxxxxxxxxxxxx>]

--- Eleu Lima Natalli <eleu.vix@zaz.com.br> escreveu:
> Alguem sabe em q site posso baixar o prog q ''caça''
>  nº primos ?

Uma técnica muito utilizada em algoritmos de criptografia RSA para
encontrar números primos grandes genéricos (não necessariamente de
mersenne e tal) é a seguinte:

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.

Você pode adquirir maiores informações no livro "Introduction to
Algorithms" de Cormen, Leiserson e Rivest.

Espero ter sido claro o suficiente.

Até mais

Vinicius Fortuna