Prime numbers generator This is a prime numbers generator class, loosely based on the sieve of Eratosthenes. It is supposed to generate a decent quantity (i.e. millions) of prime numbers.

static class PrimesGenerator
{
    private const int StartFrom = 2;

    public static IEnumerable&lt;int&gt; GetPrimes()
    {
        var number = StartFrom;
        var dividers = new List&lt;int&gt;();
        while (true)
        {
            if (!IsDividedBy(number, dividers))
            {
                yield return number;
                dividers.Add(number);
            }
            number++;
        }

        bool IsDividedBy(int inputValue, IEnumerable&lt;int&gt; increasingSeriesOfDividers)
        {
            foreach (var divider in increasingSeriesOfDividers)
            {
                if (divider * divider &gt; inputValue)
                    return false;
                if (inputValue % divider == 0)
                    return true;
            }

            return false;
        }
    }
}


For C# 6.0 or earlier IsDividedBy can be written as a private method instead of a local function.

Here's a console application I've used to estimate the generation time:

class Program
{
    static void Main(string[] args)
    {
        var stopwatch = new Stopwatch();
        stopwatch.Start();
        var primes = PrimesGenerator.GetPrimes().Take(1000000).ToList();
        stopwatch.Stop();
        Console.WriteLine(string.Join(", ", primes));
        Console.WriteLine($"Time elapsed: {stopwatch.Elapsed}");
    }
}


What I want to know:


Is there a way to get rid of the dividers list, saving the memory, without decreasing the performance? (by "performance" here I mean time needed to generate the sequence)
How can I decrease the computational complexity of this code? For now, the bigger value the current value is, the noticeably slower it works.
How this code can be improved in a broad sense?
There's a lot to be improved here.  What you call dividers would be simply called primes.  This may have loosely been inspired by a sieve, but its inner mechanics are nothing like a sieve.  It's no surprise that performance degrades with larger numbers, and if you go too high, you may run into memory issues since the dividers (or primes) keeps a list in memory.

Performance should also suffer because you check every number from 2 onward.  You could check 2 to eliminate all evens first, and then only check odd numbers after that.

We discourage one line calls here unless enclosed in braces.  So change this:

if (divider * divider &gt; inputValue)
    return false;


To this:

if (divider * divider &gt; inputValue)
{ 
    return false; 
}


You may want to investigate using a sieve.  Here are old examples:

Sieve31, my sieve of Eratosthenes returning IEnumerable&lt;int&gt;

Sieve32, a simple 32 bit sieve returning IEnumerable&lt;uint&gt; using C#

Sieve32FastV2 - A fast parallel Sieve of Eratosthenes