Re: Programa_para_achar_nºs_primos_...
Rapaz existem algoritmos que podem ser implementados para se achar primos , pelo fato de eles serem cada vez mais raros quando se vai a direita na reta real ,é muito demorado vc achar primos cada vez maiores.Desconheço um programa no mercado somente com essa finalidade.Eu acho melhor pedir a alguem que entenda melhor ,fazer um executável para vc. --- Eleu Lima Natalli <[EMAIL PROTECTED]> escreveu: > Alguem sabe em q site posso baixar o prog q ''caça'' > nº primos ? > > > []s > ___ Yahoo! GeoCities Tenha seu lugar na Web. Construa hoje mesmo sua home page no Yahoo! GeoCities. É fácil e grátis! http://br.geocities.yahoo.com/
Re: Programa_para_achar_nºs_primos_...
Ha um em http://www.mersenne.org/prime.htm []s Carlos Maçaranduba wrote: > Rapaz existem algoritmos que podem ser implementados > para se achar primos , pelo fato de eles serem cada > vez mais raros quando se vai a direita na reta real ,é > muito demorado vc achar primos cada vez > maiores.Desconheço um programa no mercado somente com > essa finalidade.Eu acho melhor pedir a alguem que > entenda melhor ,fazer um executável para vc. > > --- Eleu Lima Natalli <[EMAIL PROTECTED]> escreveu: > > Alguem sabe em q site posso baixar o prog q ''caça'' > > nº primos ? > > > > > > []s > > > > >___ > Yahoo! GeoCities > Tenha seu lugar na Web. Construa hoje mesmo sua home page no Yahoo! GeoCities. É >fácil e grátis! > http://br.geocities.yahoo.com/
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 ? 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
Re: Programa_para_achar_nºs_primos_...
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
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 ?
Não sei bem o que você tem em mente, mas em
www.mersenne.org
você pode baixar um programa que procura primos de Mersenne,
leia mais lá sobre o assunto. O programa abaixo gera primos de Proth,
primos da forma a*2^b + 1 (com a relativamente pequeno). Exemplo:
boto:~/papers/mersenne/prog%./proth1a 1 500 120
7 * 2^120 + 1 = 930459597049440326649421962412033 é primo.
231 * 2^120 + 1 = 307051667026315566640779430924759597057 é primo.
277 * 2^120 + 1 = 368196154832421696794354555697655447553 é primo.
315 * 2^120 + 1 = 418706818672248499964699223988308541441 é primo.
331 * 2^120 + 1 = 439974466604807153931160136952794054657 é primo.
Acabei de rodar este exemplo e não demorou nada perceptível.
O exemplo abaixo demorou poucos segundos.
boto:~/papers/mersenne/prog%./proth1a 1 1000 500
711 * 2^500 + 1 =
232738072221415686957937787422997226032494736619065322620162716351129243723608522005035643717855734280432414695210487553469404124514460916583116046337
é primo.
Note que estes números são _demonstravelmente_ primos e não
apenas _provavelmente_ primos.
Eu compilei o programa assim:
boto:~/papers/mersenne/prog%gcc proth1.c -lm -lgmp -Wall -o proth1a
Isto em uma máquina Linux. Deve ser fácil fazer o programa funcionar
em OS parecidos com Unix e deve ser possível até em Windows.
Há mais coisa deste tipo no livro do Gugu e meu sobre primos de Mersenne,
disponível na minha home page.
[]s, N.
===
#include
#include
#include
mpz_t pp;
int
proth(unsigned long h, unsigned long k)
{
unsigned long i;
mpz_t pm, test, aux;
extern mpz_t pp;
mpz_init(pm);
mpz_init(test);
mpz_init(aux);
mpz_ui_pow_ui(pm,(long)(2),k);
mpz_mul_ui(pm,pm,h);
mpz_fdiv_q_2exp(aux,pm,(long)(1));
mpz_add_ui(pp,pm,(long)(1));
/* Calculamos pp = hh * 2^k + 1, pm = pp - 1 e aux = (pp-1)/2. */
mpz_set_ui(test,(long)(2));
mpz_powm(test,test,aux,pp);
if ( mpz_cmp(test,pm) == 0 )
{
mpz_clear(pm);
mpz_clear(test);
mpz_clear(aux);
return(1);
}
if ( mpz_cmp_ui(test,(long)(1)) != 0 )
{
mpz_clear(pm);
mpz_clear(test);
mpz_clear(aux);
return(0);
}
for ( i = 3 ; i < 1000 ; i += 2 )
{
mpz_set_ui(test,i);
if ( mpz_probab_prime_p(test,25) )
{
mpz_powm(test,test,aux,pp);
if ( mpz_cmp(test,pm) == 0 )
{
mpz_clear(pm);
mpz_clear(test);
mpz_clear(aux);
return(1);
}
if ( mpz_cmp_ui(test,(long)(1)) != 0 )
{
mpz_clear(pm);
mpz_clear(test);
mpz_clear(aux);
return(0);
}
}
}
mpz_clear(pm);
mpz_clear(test);
mpz_clear(aux);
return(-1);
}
int
main(int argc, char *argv[])
{
int answ;
unsigned long h, hmin, hmax, k;
extern mpz_t pp;
hmin = atol(argv[1]);
hmax = atol(argv[2]);
k = atol(argv[3]);
mpz_init(pp);
for ( h = hmin ; h <= hmax ; h++ ) if ( h & 1 )
{
answ = proth(h,k);
if ( answ == 1 )
{
printf("%ld * 2^%ld + 1 = ",h,k);
mpz_out_str(stdout,10,pp);
printf(" é primo.\n");
}
else if ( answ < 0 ) printf("%ld * 2^%ld + 1: difícil...\n",h,k);
}
return(0);
}
=
Re: Programa_para_achar_nºs_primos_...
On Mon, Dec 03, 2001 at 09:10:53PM -0200, Gustavo Nunes Martins wrote: > Ha um em http://www.mersenne.org/prime.htm Btw, há um novo candidato a maior número primo conhecido sendo testado neste momento. O anúncio oficial deve sair em poucos dias no endereço acima (se tudo for confirmado, claro). Uma notícia não oficial 'vazou' que o número seria 2^13466917 - 1, com 4053945 algarismos. []s, N.
