# 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<int> GetPrimes()
{
var number = StartFrom;
var dividers = new List<int>();
while (true)
{
if (!IsDividedBy(number, dividers))
{
yield return 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?
• How is this in any way related to sieve of Eratosthenes? – paparazzo Jun 16 '18 at 11:10

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