IEnumerable de primos | ZBRA Soluções
Tags: .NET, Abstraction, OO, Performance
No meu dia a dia enquanto estou codando, cada vez mais tenho usado yield return, lambda expressions e method extensions. Os dois últimos são particularmente muito bons para garantir desacoplamento. Há uns dias atrás eu estava resolvendo alguns problemas no Project Euler e me vi várias vezes tendo que calcular uma sequência de números primos parar fazer fatoração de números inteiros.
Eu não sou especialista em calcular números primos mais sei que uma forma básica e eficiente de fazer isso de forma crescente é:
Começar com os primos 1,2,3 em uma lista
Considerar como próximos candidatos os números ímpares
Apenas tentar dividir um candidato pelo primos já conhecidos
Parar quando chegar em um primo que seja maior que a raiz do candidato
Pelo fato de ser mais eficiente processar um candidato tentando dividi-lo apenas pelos primos já conhecidos, é necessário fazer um cache dos primos já calculados. Esse é o típico problema que se resolve bem criando uma abstração simples. A primeiro coisa que me veio à cabeça foi implementar um IEnumerable de primos. Code please!
public class CachedPrimes : IEnumerable<int>
if (primes.Count == 0)
next = primes.Last();
if (!CanDivide(next))
private bool CanDivide(int next)
var sqrt = Math.Sqrt(next);
if (next % prime == 0)
Fantástico! Consegui encapsular dentro de um simples IEnumerable todo comportamento que me retorna todos os números primos existentes. De fato implentei um IEnumerable infinito, visto que a sequência de número primos é infinita. Como disse antes, não sei se é a forma mais eficiente, mas pro tipo de problema do Project Euler já da bem pro gasto. Seria relativamente fácil alterar essa classe para que ela salvasse e recuperasse a lista de primos já calculada em um arquivo no disco (obviamente tomando cuidado com sincronização, não é um código tão trivial assim, mas é relativamente fácil).
O uso dessa classe poderia ser algo mais ou menos assim:
var primes = new CachedPrimes();
foreach (var div in GetDivisors(10, primes))
foreach (var div in GetDivisors(105, primes))
foreach (var div in GetDivisors(921, primes))
private IEnumerable<long> GetDivisors(long num, CachedPrimes primes)
if (prime == num)
if (prime > num)
Conforme chamadas subsequentes vão sendo feitas para o mesmo objeto CachedPrimes a lista de primos interna vai crescendo e o tempo para achar os divisores diminui. Obviamente o IEnumerable só para quando você da um break e o cache só funciona se o mesmo objeto for reutilizado. Olhando na página do wiki da pra ver que existem formas bem mais eficientes de calcular primos em sequência. O intuito desse artigo não era discutir a melhor forma de calculá-los, mas sim mostrar como encapsular isso dentro de apenas um objeto de uma forma elegante. Tenho certeza que o mesmo conceito que demonstrei aqui neste artigo pode ser usado para outros algoritmos. A grande vantagem é a simplicidade de uso pois a classe CachedPrimes nada mais é do que um IEnumerable<long>.