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

Diferenças para "DeterminandoPrimos"

Diferenças entre as versões de 1 e 11 (10 versões de distância)
Revisão 1e 2004-10-20 04:26:54
Tamanho: 6037
Comentário:
Revisão 11e 2006-01-12 15:21:52
Tamanho: 7647
Comentário: Colocação no nome do autor
Deleções são marcadas assim. Adições são marcadas assim.
Linha 1: Linha 1:
#pragma section-numbers off Autor: MarcoAndréLopesMendes
Linha 3: Linha 3:
= 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.
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 [http://www.rsasecurity.com/rsalabs/node.asp?id=2214 RSA], utilizado no [http://www.rsasecurity.com/rsalabs/node.asp?id=2293 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.
Linha 12: Linha 10:
Lendo o Learning Python, encontrei um exemplo de implementação do algoritmo, que é o pior que poderia existir: Lendo o [http://www.oreilly.com/catalog/lpython/ Learning Python], encontrei um exemplo de implementação do algoritmo, que é o pior que poderia existir:
Linha 43: Linha 41:
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í. Por exemplo, pra determinar se 100 é primo o programa verifica todos os numeros 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.
Linha 45: Linha 43:
Alterando o programa, ele fica assim: Fazendo esta alteração, o programa fica assim:
Linha 65: Linha 63:
E o resultado melhora bastante: E o resultado, como era esperado, melhora bastante:
Linha 71: Linha 69:
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: Mas ainda São necessária smuitas 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:
Linha 77: Linha 75:
Chega-se a: E com esta alteração chega-se a:
Linha 82: Linha 80:
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. 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.
Linha 84: Linha 82:
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: Como não se sabe quantos números encontraremos, devemos deixar o programa o mais flexível possível. Em C, teriamos 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:
Linha 105: Linha 103:
#------------------------------------------------------------------------- }}}
Linha 107: Linha 105:
O resultado foi este: O resultado é este:
{{{
Linha 109: Linha 108:
}}}
Linha 110: Linha 110:
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:
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:
Linha 114: Linha 112:
#------------------------------------------------------------------------- {{{
#!python

from math import sqrt
Linha 137: Linha 139:
#------------------------------------------------------------------------- }}}
Linha 140: Linha 142:
{{{
Linha 141: Linha 144:
}}}
Linha 142: Linha 146:
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.
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).
Linha 146: Linha 148:
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.
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ício, entre emcontato comigo. Se tiver alguma coisa que está pouco "Pythonica" e pode ser melhorada, me avise também.
Linha 151: Linha 150:
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.
Uma possibilidade diferente é a utilizaçao de [http://www.google.com/search?q=teste+de+primalidade testes de primalidade].
Linha 159: Linha 152:
Um abraço
Comentário sobre a receita...
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 linguages 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 tranquila e o código ficou extremamente legivel, 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.
Linha 162: Linha 154:
== Código == ''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:
Linha 166: Linha 158:
import sys
Linha 168: Linha 159:
if __name__ == '__main__':
   print "Aqui entra o código"
from math import sqrt
Linha 171: Linha 161:
print "Primos: 2",

c, p, primos, limite = 1, 1, [2,], 1000

for numero in xrange(3,limite+1,2): #pula de dois em dois
    ehprimo = 1
    for i in primos:
        c += 1 # mudei de lugar
        if numero % i == 0:
            ehprimo = 0
            break
        if i > sqrt(numero):
            break
    if (ehprimo):
        primos.append(numero)
        print numero,
        p += 1

print "\n\nForam encontrados %d números primos." %p
print "Foram necessárias %d comparações." %c
Linha 172: Linha 182:

== Exemplo de uso ==

{{{
#!python
import sys

if __name__ == '__main__':
   print "Aqui entra o exemplo de uso. Essa seção é opcional."

}}}

Volta para CookBook.

----

Nome do autor da Receita

Autor: MarcoAndréLopesMendes

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 [http://www.rsasecurity.com/rsalabs/node.asp?id=2214 RSA], utilizado no [http://www.rsasecurity.com/rsalabs/node.asp?id=2293 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 [http://www.oreilly.com/catalog/lpython/ 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 numeros 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:

   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, como era esperado, melhora bastante:

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

Mas ainda São necessária smuitas 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 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, teriamos 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 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 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ício, entre emcontato comigo. Se tiver alguma coisa que está pouco "Pythonica" e pode ser melhorada, me avise também.

Uma possibilidade diferente é a utilizaçao de [http://www.google.com/search?q=teste+de+primalidade 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 linguages 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 tranquila e o código ficou extremamente legivel, 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