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

Diferenças para "DeterminandoPrimos"

Diferenças entre as versões de 5 e 15 (10 versões de distância)
Revisão 5e 2004-10-20 05:15:27
Tamanho: 5681
Comentário:
Revisão 15e 2008-04-07 17:05:40
Tamanho: 9383
Comentário:
Deleções são marcadas assim. Adições são marcadas assim.
Linha 1: Linha 1:
#pragma section-numbers off

= Determinando se um número é primo =
Autor: MarcoAndreLopesMendes

Atualização: o [http://devlog.waltercruz.com/ Walter Cruz] escreveu um [http://devlog.waltercruz.com/determinando_numeros_primos_em_lua artigo] inspirado nesse, resolvendo o mesmo problema em [http://www.lua.org/portugues.html Lua].
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í.

Alterando o programa, ele fica assim:
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:
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á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:
Linha 77: Linha 77:
Chega-se a:
{{{
E com esta alteração chega-se a:
{{{
Foram encontrados 168 números primos.
Linha 82: Linha 83:
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:
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:
Linha 107: Linha 108:
O resultado foi este:
{{{
O resultado é este:
{{{
Foram encontrados 168 números primos.
Linha 112: Linha 114:
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:

{{{
#!python
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:

{{{
#!python

from math import sqrt
Linha 142: Linha 147:
Foram encontrados 168 números primos.
Linha 145: Linha 151:
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.
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 [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 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:''

{{{
#!python

from math import sqrt

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
}}}

{{{
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 [http://pt.wikipedia.org/wiki/Crivo_de_Erat%C3%B3stenes 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:

{{{
#!python
def primes( n ):
    if n < 2: return []
    if n == 2: return [2]
    nums = range(3, n+1, 2)
    nums_length = (n // 2) - 1 + (n % 2)
    idx = 0
    idx_sqrtn = (int(n**0.5) - 3) // 2
    while idx <= idx_sqrtn:
        nums_at_idx = (idx << 1) + 3
        for j in xrange( idx * (nums_at_idx + 3) + 3, nums_length, nums_at_idx ):
            nums[j] = 0
        idx += 1
        while idx <= idx_sqrtn:
            if nums[idx] != 0:
                break
            idx += 1
    return [2] + [x for x in nums if x != 0]

def meu_primos(limite):
    lista_de_primos = primes(limite)
    print "Primos:", " ".join(str(x) for x in lista_de_primos)
    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.

Autor: MarcoAndreLopesMendes

Atualização: o [http://devlog.waltercruz.com/ Walter Cruz] escreveu um [http://devlog.waltercruz.com/determinando_numeros_primos_em_lua artigo] inspirado nesse, resolvendo o mesmo problema em [http://www.lua.org/portugues.html 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 [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 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:

   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á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 [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 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 [http://pt.wikipedia.org/wiki/Crivo_de_Erat%C3%B3stenes 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.