Puxa vida! Quanta coisa existe sobre verificação de números primos... Agora é só estudar!
Muito obrigado a todos! -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Nicolau C. Saldanha Sent: quarta-feira, 25 de fevereiro de 2004 12:21 To: [EMAIL PROTECTED] 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 =========================================================================