associação pythonbrasil[11] django zope/plone planet Início Logado como (Entrar)

Revisão 1e 2004-10-20 04:26:54

Excluir mensagem

DeterminandoPrimos

Determinando se um número é primo

Os números primos me fascinam há muito tempo. Ter estudado Criptografia, só aumentou este interesse. É comum eu passar aos meus alunos que façam um programa para determinar se um numero é primo. Os primos são úteis em várias áreas da Computação, como é o caso do algoritmo RSA, utilizado no SSL. A [http://www.matematica.br/historia/nprimos.html explicação histórica]sobre os primos é também bem interessante. Por fim, a lógica do programa é boa para desenvolver algumas habilidades para quem está aprendendo a programar.

Geralmente lanço como desafio que os alunos encontrem os primos menores que 1000, informando quantos são e quantas vezes o if mais interno do programa foi executado. É uma forma de ensiná-los a pensar em termos de otimização de código e desempenho.

Eu já havia implementado versões pouco otimizadas em C, mas resolvi ir mais além em Python, uma vez que a linguagem realmente estimula a seguir em frente. Em C, chegaria num ponto que eu teria que utilizar uma lista encadeada, e só pensar nisto já desanima...

Lendo o Learning Python, encontrei um exemplo de implementação do algoritmo, que é o pior que poderia existir:

   1 limite = 1000
   2 numero = 2
   3 c = 1
   4 p = 0
   5 print "Primos: ",
   6 while numero < 1000:
   7     i = numero -1
   8     while i > 1:
   9         if numero % i == 0: break
  10         i -= 1
  11         c += 1
  12     else:
  13         print numero,
  14         p += 1
  15     numero += 1
  16 
  17 print "\n\nForam encontrados %d números primos." %p
  18 print "Foram necessárias %d comparações." %c

O resultado obtido é:

Foram encontrados 168 números primos.
Foram necessárias 333723 comparações.

Esta versão verifica todos os números, de cima pra baixo até encontrar uma divisão exata. Por exemplo, pra verificar se 100 é primo ele verifica todos os numeros até 50, pra descobrir que 100 nao é primo. Seria muito mais fácil verificar de baixo pra cima e saber que 100/2 dá divisão exata, parando por aí.

Alterando o programa, ele fica assim:

   1 limite = 1000
   2 c = 1
   3 p = 0
   4 print "Primos: ",
   5 for numero in xrange(2, limite+1):
   6     for i in xrange(2,numero):
   7         if numero % i == 0: break
   8         c += 1
   9     else:
  10         print numero,
  11         p += 1
  12 
  13 print "\n\nForam encontrados %d números primos." %p
  14 print "Foram necessárias %d comparações." %c

E o resultado melhora bastante:

Foram encontrados 168 números primos.
Foram necessárias 77192 comparações.

Mas ainda é muita coisa. A próxima idéia que surge e não verificar todos, mas apenas a metade dos números. Alterando o for interno para:

for i in xrange(2,(numero/2)+1):

Chega-se a:

Foram necessárias 39213 comparações.

Daria para tentar melhorar umpouco mais usando esta abordagem, mas não se iria muito mais longe. Uma abordagem diferente seria armazenar os primos já encontrados e utilizá-los para descobrir os demais, uma vez que não é necessário testar todos os números, mas apenas os primos menores que o número. Pela definição, todos os números não primos (compostos) são formados por primos, então o teste se torna bem menor.

Como nao se sabe quantos números encontraremos, teriamos que criar (em C) um array grande (simples e deselegante) ou uma lista encadeada,(elegante e complexo). De qualquer forma, isto levaria algumas lnhas para ser feito. Em Python, usei uma lista, assim:

   1 limite = 1000
   2 
   3 print "Primos: 2",
   4 c = 1
   5 p = 1
   6 primos = [2,]
   7 for numero in xrange(3,limite+1):
   8     for i in primos:
   9         if numero % i == 0: break
  10         c += 1
  11     else:
  12         primos.append(numero)
  13         print numero,
  14         p += 1
  15 
  16 print "\n\nForam encontrados %d números primos." %p
  17 print "Foram necessárias %d comparações." %c
  18 #-------------------------------------------------------------------------
  19 
  20 O resultado foi este:
  21 Foram necessárias 14790 comparações.
  22 
  23 Como última melhoria, passei a não verificar todos os primos menores
  24 que o número, mas apenas os números menores que a raiz quadrada do
  25 número:
  26 
  27 #-------------------------------------------------------------------------
  28 limite = 1000
  29 
  30 print "Primos: 2",
  31 c = 1
  32 p = 1
  33 primos = [2,]
  34 for numero in xrange(3,limite+1):
  35     ehprimo = 1
  36     for i in primos:
  37         if numero % i == 0:
  38             ehprimo = 0
  39             break
  40         if i > sqrt(numero):
  41             break
  42         c += 1
  43     if (ehprimo):
  44         primos.append(numero)
  45         print numero,
  46         p += 1
  47 
  48 print "\n\nForam encontrados %d números primos." %p
  49 print "Foram necessárias %d comparações." %c
  50 #-------------------------------------------------------------------------
  51 
  52 O resultado é muito melhor ainda:
  53 Foram necessárias 1971 comparações.
  54 
  55 Resumindo:isto significa que eu consigo descobrir todos os primos
  56 menores que 1000 fazendo apenas 1971 comparações, contra as 333723 que
  57 seriam necessárias utilizando o algoritmo do livro.
  58 
  59 Deste ponto eu não sei mais pra onde ir. Se alguem souber uma forma
  60 ainda mais eficiente de resolver este problema, eu gostaria de
  61 conhecer. Se tiver alguma coisa que está pouco "pythonica", me avisem
  62 também.
  63 
  64 Minha conclusão é de que em Python eu pude implementar uma idéia que
  65 eu já tinha na cabeça há muito tempo, mas não implementava por que a
  66 linguagem não me animava. Com Pyhton, não tive problemas com a
  67 linguagem em nenhum momento. A implementação foi tranquila e o código
  68 ficou extremamente legivel, nao sendo difícil mesmo um iniciante de
  69 compreende-lo. A linguagem realmente "não fica na frente". Para mim
  70 foi mais uma confirmação de que a escolha da linguagem está correta.
  71 
  72 Um abraço
  73 Comentário sobre a receita...
  74 
  75 == Código ==
  76 
  77 {{{
  78 #!python
  79 import sys
  80 
  81 if __name__ == '__main__':
  82    print "Aqui entra o código"

Exemplo de uso

   1 import sys
   2 
   3 if __name__ == '__main__':
   4    print "Aqui entra o exemplo de uso. Essa seção é opcional."

Volta para CookBook.


Nome do autor da Receita