Prime number generation in C#

prime_number_generation.md

Inspired by YouTube video, Advanced Topics in Programming Languages: Concurrency/message passing Newsqueak.

public IEnumerable<int> Primes(int max)
{
    int count = 0;
    int candidatePrime = 2;
    var primes = new List<int>(max);

    while (count < max)
    {
        while (primes.Any(prime => candidatePrime % prime == 0)) candidatePrime++;

        yield return candidatePrime;

        primes.Add(candidatePrime);
        count++;
    }
}

Thoughts about the implementation:

• We don't really need to pass in max or maintain count:
  • The caller could/should be responsible for breaking out of the iteration
• We don't need to set the initial capacity of the List
  • we should trust the underlying List implementation to be efficient; or
  • we could build a custom implementation to efficiently manange the memory
• Using Linq's Any() is really nice as I don't need to put any thought into when to increment candidatePrime
  • A custom implementation would likely be faster

Another implementation of prime generation can be seen here: https://gist.github.com/mcmullm2-dcu/648f08f3c4e96e368cbf7f4c47e0cb74

prime_number_generation_alt.md

This was my first attempt at creating a prime generator based on YouTube video, Advanced Topics in Programming Languages: Concurrency/message passing Newsqueak.

This implementation closely matches the implenentation that Newsqueak/Go channels would provide.
The Primes method creates a new PrimeFilter for each discovered prime.
A PrimeFilter filters out any value that is divisible by the discovered prime.

The drawback to this approach is the excessive amount of allocations and method calls to generate the final list of primes:

• A PrimeFilter is crated for each prime, with a reference to a parent PrimeFilter
• For each integer, Next() is called at least once on each instance of PrimeFilter and also each time candidatePrime is divisible by Prime

Here is the implementation:

public interface IPrimeFilter
{
    int Next();
}

public class PrimeFilter : IPrimeFilter
{
    private IPrimeFilter ParentPrimeFilter { get; }
    private int Prime { get; }

    public PrimeFilter(int prime, IPrimeFilter parentPrimeFilter)
    {
        ParentPrimeFilter = parentPrimeFilter;
        Prime = prime;
    }

    public int Next()
    {
        int candidatePrime = ParentPrimeFilter.Next();

        while (candidatePrime % Prime == 0) candidatePrime = ParentPrimeFilter.Next();

        return candidatePrime;
    }
}

private class BasePrimeFilter : IPrimeFilter
{
    private int CandidatePrime = 2;

    /// <inheritdoc />
    public int Next()
    {
        return CandidatePrime++;
    }
}


public void Primes(int max)
{
    int count = 0;
    IPrimeFilter filter = new BasePrimeFilter();

    while (count < max)
    {
        var prime = filter.Next();
        
        yield return prime;
        
        filter = new PrimeFilter(prime, filter);
        count++;
    }
}