2
\$\begingroup\$

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?
\$\endgroup\$
  • 1
    \$\begingroup\$ How is this in any way related to sieve of Eratosthenes? \$\endgroup\$ – paparazzo Jun 16 '18 at 11:10
3
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.