IEnumerable de primos

Publicado por Alexandre Cunha
16/10/2011
Categoria:
Tags: , , ,

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>
{
    private List<int> primes = new List<int>();

    public IEnumerator<int> GetEnumerator()
    {
        yield return 1;
        yield return 2;
        foreach (var prime in primes)
            yield return prime;
        int next = 3;
        if (primes.Count == 0)
        {
            primes.Add(3);
            yield return 3;
        }
        else
        {
            next = primes.Last();
        }
        while (true)
        {
            next += 2;
            if (!CanDivide(next))
            {
                primes.Add(next);
                yield return next;
            }
        }
    }

    private bool CanDivide(int next)
    {
        var sqrt = Math.Sqrt(next);
        foreach (var prime in primes)
        {
            if (next % prime == 0)
                return true;
            if (prime > sqrt)
                break;
        }
        return false;
    }
}

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:


private void DoIt()
{
    var primes = new CachedPrimes();

    foreach (var div in GetDivisors(10, primes))
        Console.WriteLine(div);

    foreach (var div in GetDivisors(105, primes))
        Console.WriteLine(div);

    foreach (var div in GetDivisors(921, primes))
        Console.WriteLine(div);
}

private IEnumerable<long> GetDivisors(long num, CachedPrimes primes)
{
    foreach (var prime in primes)
    {
        if (num % prime == 0)
            yield return prime;
        if (prime == num)
            break;
        if (prime > num)
        {
            yield return num;
            break;
        }
    }
}

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>.

CQD.





Desenvolvido por hacklab/ com WordPress