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?