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

Diferenças para "DeterminandoPrimos"

Diferenças entre as versões de 2 e 8 (6 versões de distância)
Revisão 2e 2004-10-20 04:30:24
Tamanho: 5559
Comentário:
Revisão 8e 2005-04-19 17:48:47
Tamanho: 7778
Editor: 201-2-197-95
Comentário:
Deleções são marcadas assim. Adições são marcadas assim.
Linha 5: Linha 5:
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 12:
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 43:
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 45:
Alterando o programa, ele fica assim: Fazendo esta alteração, o programa fica assim:
Linha 65: Linha 65:
E o resultado melhora bastante: E o resultado, como era esperado, melhora bastante:
Linha 71: Linha 71:
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 77:
Chega-se a: E com esta alteração chega-se a:
Linha 82: Linha 82:
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 84:
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 107: Linha 107:
O resultado foi este: O resultado é este:
Linha 112: Linha 112:
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 116: Linha 116:

from math import sqrt
Linha 145: Linha 148:
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 147: Linha 150:
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 149: Linha 152:
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 152: Linha 154:
Um abraço 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 156: Linha 158:
Volta para CookBook. Volta para DocumentaçãoPython.

----
''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:

{{{
#!python

from math import sqrt

print "Primos: 2",
c = 1
p = 1
primos = [2,]
limite = 1000

for numero in xrange(3,limite+1,2): # 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
}}}

-- PedroDeMedeiros.''

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 [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.

MarcoAndréLopesMendes

Volta para DocumentaçãoPython.


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 c = 1
   5 p = 1
   6 primos = [2,]
   7 limite = 1000
   8 
   9 for numero in xrange(3,limite+1,2): # de dois em dois
  10     ehprimo = 1
  11     for i in primos:
  12         c += 1 # mudei de lugar
  13         if numero % i == 0:
  14             ehprimo = 0
  15             break
  16         if i > sqrt(numero):
  17             break
  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

-- PedroDeMedeiros.