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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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:
- Escreva uma lista dos números entre 2 e o maior número que você quer testar a primalidade. Vamos chamá-la de lista1;
- 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;
- Remova o 2 e todos os múltiplos dele da lista1;
- O primeiro número que sobrar da lista1 é primo. Escreva ele na lista2;
- 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;
- 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).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | 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 🙂