30 de setembro de 2008

O Crivo de Eratóstenes em Python


Sabe aqueles problemas que te instigam a resolvê-los? Hoje eu encontrei um.

Estou tentando me aprimorar na linguagem Python e tenho usado o livro Python: How to Program para isso. No capítulo 5, que trata de listas, tuplas e dicionários, mais precisamente nos exercícios no final do capítulo, eu encontrei um problema bem desafiador: O Crivo de Eratóstenes.

Para quem não sabe, crivo significa, dentre outras coisas, peneira; e Eratóstenes, de acordo com a Wikipédia, foi um matemático, bibliotecário e astrônomo grego, que viveu entre os anos de 276 e 194 aC. O Crivo de Eratóstenes é uma forma bem interessante de se calcular números primos e o algoritmo é relativamente simples:
  1. Considere um vetor de números de 2 até o limite imposto pela pessoa que deseja calcular.
  2. Calcule a raíz quadrada do limite escolhido, arredondando-a para baixo e guarde este valor.
  3. Começando do primeiro item (2), remova todos os números que sejam múltiplos dele.
  4. Avance para o próximo item e repita o passo 3, até o número calculado no passo 2.
  5. Os números que sobrarem no vetor são primos.

Além de interessante, o Crivo de Erastótenes é uma ótima forma de se experimentar a utilização de listas e estruturas de repetição, principalmente com relação ao limite de iteração destas.

Para quem ainda não entendeu o funcionamento do algoritmo, abaixo segue uma imagem retirada da Wikipédia, que mostra graficamente como o mesmo funciona (considerando um limite igual a 120). Logo a seguir, segue o código que eu fiz em Python para resolver o problema proposto. É de um iniciante na linguagem, eu sei, mas faz direitinho seu trabalho. Ao executá-lo, será pedido o valor limite e após apertar Enter, a mágica acontece e o resultado é impresso na tela.
O código fonte está em inglês!


Figura 1. O Crivo de Eratóstenes graficamente.


#!/usr/bin/env python

# Sieve of Eratosthenes
#    Calculate and print on the screen the numbers that compose the sieve
# of Eratosthenes.
#
# AUTHOR: Jose' Lopes de Oliveira Ju'nior - http://versaopropria.blogspot.com
#
# CONTACT: jlojunior _at_ gmail _dot_ com
#
# DATE: 2008-09-30
#
# LICENCE: GPLv3 - http://www.gnu.org/licenses/gpl.html
#
#   For more information about the Sieve of Eratosthenes, please visit its page
# on Wikipedia: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
###############################################################################

import math

def fill_list(lim=10):

    """Fill a list with values from 2 to lim.

    Requires the limit.

    """

    list = []

    for index in range(2, lim + 1):
        list.append(index)

    return list

def remove_zeros(list):

    """Remove zeros from the list passed.

    Requires the list of integers.

    """

    list2 = []

    for index in range(len(list)):
        if list[index]:
            list2.append(list[index])

    return list2

def sieve_of_eratosthenes(lim=10):

    """Calculate the Sieve of Eratosthenes.

    Returns a list with zeros in place of number which
    aren't prime. Only the prime numbers are different
    of zero.

    """

    # Create the list of values and calculate the square
    # +root of the limit.
    sieve = fill_list(lim)
    limit = int(math.sqrt(lim))

    # The first 'for' structure iterates until de square root
    # +of the limit.The second 'for' structure iterates until
    # +the limit.
    for index1 in range(0, limit):
        # Jump zeros.
        if not sieve[index1]:
            continue

        for index2 in range(index1 + 1, lim - 1):
            if sieve[index2] and (not (sieve[index2] % sieve[index1])):
                sieve[index2] = 0

    return remove_zeros(sieve)


# Main
print sieve_of_eratosthenes(int(raw_input("Enter with the limit \
value for the sieve: ")))
Código 1. Exemplo do Crivo de Eratóstenes em Python.

Espero que não tenham ficado mistérios sobre o assunto, além do fato de que algo tão complexo tenha sido descoberto há tanto tempo... :D

Leia Também

11 comentários:

  1. Salve, Elcio!
    Engraçado, pois eu já havia acessado o fechaTAG! :)
    Fiz esse código quando tava bem no início da aprendizagem de Python. Atualmente eu mudaria algumas coisas, como a função extra só pra preencher o vetor, mas confesso que a sua solução para a raíz quadrada foi foda! Foda mesmo! Evitou chamar o módulo Math! Aprendizado pra mim!
    Já o lambda(), eu não entendo o funcionamento e pra mim é uma caixa preta. Ainda não me dei bem com programação funcional...
    De qualquer forma, obrigado por compartilhar o conhecimento! Essa da raíz eu não esqueço mais!
    Abraço, cara!

    ResponderExcluir
  2. muito bom isso de partilhar conhecimento , eu tou resolvendo este mesmo problema em java (mais dificil ) e ja fiquei com umas luzes de como resolver.

    ResponderExcluir
  3. @Anônimo Valeu! A ideia é essa! :-)

    ResponderExcluir
  4. esta versão: http://gist.github.com/363882
    pode ser considerada um algoritmo destes?

    ResponderExcluir
  5. @voyag3r
    Claro que sim! É uma forma muito mais "pythônica" que a minha (lembrando que o algoritmo desta postagem foi um dos exercícios que eu fiz para aprender a linguagem Python).
    Parabéns!
    Abraço!

    PS: Legal você usar o GitHub! Sou usuário e fã do serviço! Minha página lá é http://github.com/joselopes

    ResponderExcluir
  6. nada a ver,que porfavor!

    ResponderExcluir
  7. TA DOIDOOOOOOOOOOOOOOOOOO
    COLOCA PELOMENOS UM EXEMPLO QUE PRESTE




    UIIIIIIIIIIIIIII SÓOOOOOOOOOOO!!!!!!!!!!!!!!

    ResponderExcluir
  8. TA DOIDO SEUUUUUUUUUUUUU
    TAPADO BURROOOOOOOOOOOOOOOOOOOOO



    TAPADOOOOOOO










    ,

    ResponderExcluir
  9. SOU PROFESSORA NÃO E QUE EU QUERA FALAR MAU DE VOCÊ MAIS ISSO QUE ESCREVEU NÃO TEM NADA VERRRRRRRRRRRR


    PRECISSA VOLTAR PARA ESCOLA!!!!!!!

    ENDICO ESCOLA LAURA VICUÑA

    ResponderExcluir