Autor: MarcoAndreLopesMendes
Atualização: o Walter Cruz escreveu um artigo inspirado nesse, resolvendo o mesmo problema em Lua.
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 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 determinar se 100 é primo o programa verifica todos os números até 50, para então descobrir que 100 não é primo. Seria muito mais eficiente verificar de baixo pra cima e saber que 100/2 dá divisão exata, parando imediatamente o teste.
Fazendo esta alteração, o programa fica assim:
E o resultado, como era esperado, melhora bastante:
Foram encontrados 168 números primos. Foram necessárias 77192 comparações.
Mas ainda São necessárias muitas comparações. A próxima idéia que surge e não verificar todos, mas apenas a metade dos números. Alterando o for interno obtemos:
for i in xrange(2,(numero/2)+1):
E com esta alteração chega-se a:
Foram encontrados 168 números primos. Foram necessárias 39213 comparações.
Daria para tentar melhorar um pouco mais usando seguindo esta abordagem, mas não se iria muito mais longe. Uma abordagem diferente seria armazenar os primos já encontrados e utilizá-los para determinar 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 não se sabe quantos números encontraremos, devemos deixar o programa o mais flexível possível. Em C, teríamos que criar um array grande (simples, porém deselegante e pouco flexível) ou uma lista encadeada, (elegante e flexível, porém complexo). De qualquer forma, qualquer uma das abordagens exigiria várias linhas de código para ser implementada. Em Python, podemos utilizar 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 é este:
Foram encontrados 168 números primos. Foram necessárias 14790 comparações.
Como última melhoria, podemos passar 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 from math import sqrt
2
3 limite = 1000
4
5 print "Primos: 2",
6 c = 1
7 p = 1
8 primos = [2,]
9 for numero in xrange(3,limite+1):
10 ehprimo = 1
11 for i in primos:
12 if numero % i == 0:
13 ehprimo = 0
14 break
15 if i > sqrt(numero):
16 break
17 c += 1
18 if (ehprimo):
19 primos.append(numero)
20 print numero,
21 p += 1
22
23 print "\n\nForam encontrados %d números primos." %p
24 print "Foram necessárias %d comparações." %c
O resultado é muito melhor ainda:
Foram encontrados 168 números primos. Foram necessárias 1971 comparações.
Resumindo: isto significa que é possível determinar todos os primos menores que 1000 fazendo apenas 1971 comparações, contra as 333723 que seriam necessárias utilizando o pior algoritmo, encontrado no livro (encontrei mais tarde um algoritmo ainda pior, onde o laço não saia no momento em que a primeira divisão exata ocorria, mas fazia todas as divisões entre 1 e o número).
Deste ponto em diante eu não sei mais pra onde ir. Se você souber de uma forma ainda mais eficiente de resolver este problema, seguindo a mesma linha de raciocínio, entre em contato comigo. Se tiver alguma coisa que está pouco "Pythonica" e pode ser melhorada, me avise também.
Uma possibilidade diferente é a utilização de testes de primalidade.
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 as linguagens que eu conhecia não me animavam a fazê-lo. Com Python, não tive problemas com a linguagem em nenhum momento. A implementação foi tranqüila e o código ficou extremamente legível, não sendo difícil mesmo um iniciante de compreendê-lo. A linguagem realmente "não fica na frente". Para mim foi mais uma confirmação de que a escolha da linguagem foi correta.
Acho que o teste de comparações não está exatamente correto, porque a comparação não é contada quando um primo divide o número testado, enquanto que, para fins de teste de otimização, essa contagem devia ser realizada. Eu colocaria, então, o c += 1 no começo do laço e não no final. Há uma outra otimização faltando que diminui o número de testes, que é fazer o laço externo contando apenas os números ímpares (ou seja, começando de um número ímpar, contando de dois em dois). O código com todas as mudanças que mencionei ficaria assim portanto:
1 from math import sqrt
2
3 print "Primos: 2",
4
5 c, p, primos, limite = 1, 1, [2,], 1000
6
7 for numero in xrange(3,limite+1,2): #pula de dois em dois
8 ehprimo = 1
9 for i in primos:
10 c += 1 # mudei de lugar
11 if numero % i == 0:
12 ehprimo = 0
13 break
14 if i > sqrt(numero):
15 break
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
Foram encontrados 168 números primos. Foram necessárias 2470 comparações.
Nota (por ffao): O algoritmo mais conhecido para gerar números primos é o Crivo de Eratóstenes, que ao invés de pegar os números possíveis e checar se são primos, pega os números primos já encontrados e deleta todos os múltiplos. Uma possível implementação é a seguinte:
1 def primes( n ):
2 if n < 2: return []
3 if n == 2: return [2]
4 nums = range(3, n+1, 2)
5 nums_length = (n // 2) - 1 + (n % 2)
6 idx = 0
7 idx_sqrtn = (int(n**0.5) - 3) // 2
8 while idx <= idx_sqrtn:
9 nums_at_idx = (idx << 1) + 3
10 for j in xrange( idx * (nums_at_idx + 3) + 3, nums_length, nums_at_idx ):
11 nums[j] = 0
12 idx += 1
13 while idx <= idx_sqrtn:
14 if nums[idx] != 0:
15 break
16 idx += 1
17 return [2] + [x for x in nums if x != 0]
18
19 def meu_primos(limite):
20 lista_de_primos = primes(limite)
21 print "Primos:", " ".join(str(x) for x in lista_de_primos)
22 print "\n\nForam encontrados %d números primos." % len(lista_de_primos)
Para mostrar todos os primos abaixo de 1000, use meu_primos(1000). Esse algoritmo chega a ser umas 20 vezes mais rápido do que o descrito acima.
