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

Diferenças para "DeterminandoPrimos"

Diferenças entre as versões de 6 e 14 (8 versões de distância)
Revisão 6e 2004-10-20 05:52:41
Tamanho: 6421
Comentário:
Revisão 14e 2007-11-24 22:32:48
Tamanho: 9145
Editor: ffao
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
Linha 43: Linha 41:
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. 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.
Linha 71: Linha 69:
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: 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 79: Linha 77:
Foram encontrados 168 números primos.
Linha 84: Linha 83:
Como não se sabe quantos números encontraremos, deemos 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: 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 109: Linha 108:
Foram encontrados 168 números primos.
Linha 116: Linha 116:

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

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.