[obm-l] RE: [obm-l] Re: [obm-l] RE: [obm-l] RE: [obm-l] N�mero Primo

["David" <david-obm@xxxxxxxxxxxx>]

Puxa vida! Quanta coisa existe sobre verifica��o
de n�meros primos... Agora � s� estudar!

Muito obrigado a todos!


-----Original Message-----
From: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br] On
Behalf Of Nicolau C. Saldanha
Sent: quarta-feira, 25 de fevereiro de 2004 12:21
To: obm-l@mat.puc-rio.br
Subject: [obm-l] Re: [obm-l] RE: [obm-l] RE: [obm-l] N�mero Primo

On Wed, Feb 25, 2004 at 01:34:19AM -0300, David wrote:
> 
> >David wrote:
> >> Mas tipo, serah q existe algum algoritmo
> >> q mude o passo da iteracao para pular alguns
> >> numeros durante os testes? Ou eu vo ter q testar
> >> 2,3,4,5,6,7,8,...,sqrt(7919) um-a-um mesmo?
> 
> >	Bem, voc� n�o precisa testar todos os n�meros...
> > s� os primos menores que sqrt(7919) j� s�o suficientes !
> 
> Entendi... mas como eu sei que um numero menor que sqrt(7919) eh
> primo ou nao pra saber se eu devo testar ele ou nao? Desse jeito
> eu acabo tendo q testar todos os menores q sqrt(7919)..
> 
> Exemplo: eu tenho q testar se ele eh divisivel por 16, pois eu nao vou
> saber se 16 eh primo ou nao antes de testar 16 dividindo
1,2,...,sqrt(16)..
> nesse caso seria melhor testar logo de cara se 7919 eh divisivel por 16..
> 
> Bem... em todo caso essa dica do sqrt(7919) ja ajuda *muito*..
> Obrigado. ;)

Depois de testar que 7919 n�o � m�ltiplo de 2 nem de 3 basta testar
os n�meros da forma 6n +- 1 (5, 7, 11, 13, 17, 19, 23, 25, ...)
pois os outros claramente n�o s�o primos. Note que na pequena lista
acima o primeiro n�mero *n�o* primo que aparece � 25: quanto mais
voc� avan�ar, mais raros v�o ficar os primos mas sendo 7919 relativamente
pequeno o desperd�cio de tempo n�o ser� t�o grande assim.

Para um n�mero pequeno como 7919 isto talvez seja a melhor
coisa a fazer. Mas d� uma olhada tamb�m no meu livro com o Gugu
(Primos de Mersenne e..., est� na minha home page e voc� tamb�m pode
encomendar do Impa; a minha home page aparece no rodap� de todas as
mensagens)
e no trabalho do Agrawal e os alunos indianos dele que provaram
que existe um algoritmo surpreendentemente simples que verifica
em tempo polinomial no n�mero de algarismos se um inteiro � primo ou n�o:
procure por Agrawal PRIMES no google para ver um monte de coisa.
Alguns links:
http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html
http://www.cse.iitk.ac.uk/news/primality.html

Um assunto importante e simples s�o os testes de primalidade baseados
no pequeno teorema de Fermat. No seu caso voc� calcularia 2^7918 mod 7919
(esta conta � bem mais f�cil de fazer do que pode parecer a primeira vista):
se der qualquer coisa diferente de 1 o n�mero � composto (sabemos disso
mesmo *sem* sabermos fatorar o n�mero!) e se der 1 o n�mero � *quase*
certamente primo. Se der 1 mas voc� ainda estiver desconfiado voc� pode
tentar 3^7918 mod 7919. Se voc� precisar ter *certeza* de que o n�mero
� primo � que d� um pouco mais de trabalho.

Algu�m mencionou a fun��o isprime() do matlab. Eu n�o estou familiarizado
com o matlab, mas para n�meros maiores do que 7919 eu recomendaria verificar
as instru��es com cuidado se voc� precisar ter certeza se o n�mero � primo.
No Maple 9 a fun��o isprime() s� diz que o n�mero � quase-certamente-primo:


Description
- The function isprime is a probabilistic primality testing routine.

- It returns false if n is shown to be composite within one strong
  pseudo-primality test and one Lucas test and returns true otherwise. If
  isprime returns true, n is ``very probably'' prime - see Knuth ``The art
of
  computer programming'', Vol 2, 2nd edition, Section 4.5.4, Algorithm P for
a
  reference and H. Riesel, ``Prime numbers and computer methods for
  factorization''. No counter example is known and it has been conjectured
  that such a counter example must be hundreds of digits long.


Provavelmente dentro de pouco tempo estes programas implementar�o o
algoritmo de Agrawal (ou equivalente) mas parece que ainda n�o.

[]s, N.
=========================================================================
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
=========================================================================