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

O resultado foi este:

Foram necessárias 14790 comparações.

Como última melhoria, passei a não verificar todos os primos menores que o número, mas apenas os números menores que a raiz quadrada do número:

   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     ehprimo = 1
   9     for i in primos:
  10         if numero % i == 0:
  11             ehprimo = 0
  12             break
  13         if i > sqrt(numero):
  14             break
  15         c += 1
  16     if (ehprimo):
  17         primos.append(numero)
  18         print numero,
  19         p += 1
  20 
  21 print "\n\nForam encontrados %d números primos." %p
  22 print "Foram necessárias %d comparações." %c

O resultado é muito melhor ainda:

Foram necessárias 1971 comparações.

Resumindo: isto significa que eu consigo descobrir todos os primos menores que 1000 fazendo apenas 1971 comparações, contra as 333723 que seriam necessárias utilizando o algoritmo do livro.

Deste ponto eu não sei mais pra onde ir. Se alguem souber uma forma ainda mais eficiente de resolver este problema, eu gostaria de conhecer. Se tiver alguma coisa que está pouco "pythonica", me avisem também.

Minha conclusão é de que em Python eu pude implementar uma idéia que eu já tinha na cabeça há muito tempo, mas não implementava por que a linguagem não me animava. Com Pyhton, não tive problemas com a linguagem em nenhum momento. A implementação foi tranquila e o código ficou extremamente legivel, nao sendo difícil mesmo um iniciante de compreende-lo. A linguagem realmente "não fica na frente". Para mim foi mais uma confirmação de que a escolha da linguagem está correta.

Um abraço

MarcoAndréLopesMendes

Volta para DocumentaçãoPython.