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

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

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
=========================================================================