Prime numbers generator

Question

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<int> GetPrimes()
    {
        var number = StartFrom;
        var dividers = new List<int>();
        while (true)
        {
            if (!IsDividedBy(number, dividers))
            {
                yield return number;
                dividers.Add(number);
            }
            number++;
        }

        bool IsDividedBy(int inputValue, IEnumerable<int> increasingSeriesOfDividers)
        {
            foreach (var divider in increasingSeriesOfDividers)
            {
                if (divider * divider > 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?

Answer 1

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 > inputValue)
    return false;

To this:

if (divider * divider > inputValue)
{ 
    return false; 
}

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

Sieve31, my sieve of Eratosthenes returning IEnumerable<int>

Sieve32, a simple 32 bit sieve returning IEnumerable<uint> using C#

Sieve32FastV2 - A fast parallel Sieve of Eratosthenes