Crivo de Eratóstenes em Python

Estou fazendo os desafios do Projeto Euler e nos dez primeiros já vi três com números primos. Meu primeiro algoritmo ingenuamente testava a primalidade de um número tentando dividí-lo por todos os números menores que ele.

Uma lista com 1.000 números primos dessa maneira gera em pouco menos de um segundo no meu computador. Já 2.000, mais de 9 segundos. E 10.001, como pedido por um dos desafios, eu nem tive paciência de esperar os cálculos acabarem. Minha primeira implementação foi a seguinte:

def primo(n):
    for i in xrange(2, n):
        if n % i == 0:
            return False
    return True

primo_lista = []
n = 1
while 1:
    if primo(n):
        primo_lista.append(n)
        if len(primo_lista) == 1000:
            break
    n = n + 1

Pocurando por métodos mais velozes achei dois, o Crivo de Eratóstenes e o Crivo de Atkin. O primeiro é mais simples, então decidi implementá-lo. O Crivo de Eratóstones é definido assim:

1. Escreva uma lista dos números entre 2 e o maior número que você quer testar a primalidade. Vamos chamá-la de lista1;
2. Escreva o número 2, o primeiro número primo, em outra lista que conterá os números primos encontrados. Vamos chamá-la de lista2;
3. Remova o 2 e todos os múltiplos dele da lista1;
4. O primeiro número que sobrar da lista1 é primo. Escreva ele na lista2;
5. Remova essa número e todos os seus múltiplos da lista1. A remoção pode começar da raiz quadrada do número, já que múltiplos menores foram removidos em passos anteriores;
6. Repita os passos de 4 a 6 até não restarem mais números na lista1;

A classe a seguir, escrita em Python, retorna uma lista com todos os números primos entre 2 e um número especificado (max_n).

max_n = 50

class CrivoDeEratostenes:
    def __init__(self, max_n):
        self.lista = range(2, max_n + 1)
        self.primo_lista = [2]
        self.crivo()
        
    def crivo(self):
        primo_n = self.lista[0]
        max_n = self.lista[-1] + 1
        self.lista.remove(primo_n)
        for n in self.lista:
            if n % primo_n == 0:
                self.lista.remove(n)
        if len(self.lista) > 0:
            self.primo_lista.append(self.lista[0])
            return self.crivo()
        else:
            return self.primo_lista


print CrivoDeEratostenes(max_n).primo_lista

# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Pesquisando sobre Eratóstenes na Internet, descobri que ele foi um animal. O grego viveu dois séculos antes de Cristo e conseguiu calcular com 16% de erro a circunferência da Terra. Leu nos papiros de Biblioteca de Alexandria (aonde foi Diretor) que o sol iluminava o fundo de um poço na cidade de Siena (hoje Assuã) ao meio dia do dia mais longo (o solstício) no verão daquele cidade, em 21 de Junho. Ou seja, a luz fazia um ângulo reto com a Terra.

Mas no dia 21 de Junho, quando era meio dia em Siena, o Sol projetava sombras em Alexandria. Eratóstenes conclui então que a Terra era redonda. O ângulo das sombras deu 7º12′, quase 1/50 dos 360º de uma circunferência, então a distância entre Alexandria e Siena multiplicada por 50 seria a circunferência do planeta.

Mandou um pessoal percorrer essa distância e eles voltaram com 925km. E 50 vezes 925 é 46.250 km, enquanto a Terra tem 40.076 km.

Queria crescer de novo pra ser igual a ele 🙂