Prime number generation in C#

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++; } }

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++;
    }
}

br3nt/prime_number_generation.md

Select an option

No results found

Select an option

No results found