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

• Destrinchador de IPs em Java – Um Applet que obtém informações sobre um endereço IP e sua máscara.
• O Zen de Python – Um pequeno texto, inserido no próprio interpretador da linguagem, que elucida boas práticas de programação.
• Eclipse com Suporte a Python no OS X – Da instalação da IDE à execução de um código Python, tudo desvendado.