Custom Prime Sieve

Question

I've come up with a prime number finder I call the "Progressive Sieve". I wouldn't doubt it if this has already been thought of. Anyway, here is the idea, an implementation in C#, and benchmarks:

Premise: A number is prime if it cannot be divided evenly by any prime number below its square root.

Implementation:

static List<long> ProgressiveSieve(long bound)
    {
        List<long> primes = new List<long>() { 3 }; // start it with 3

        for (long i = 5; i < bound; i += 2) // ignore even values, because they will never be prime except 2
        {
            long sqrt = (long) Math.Sqrt(i);
            foreach (long j in primes)
            {
                if (j > sqrt) // if j gets above the square root, then i must be prime
                {
                    primes.Add(i);
                    break;
                }

                if (i % j == 0) // i is evenly divisible, no need to continue checking
                {
                    break;
                }
            }
        }

        return (new List<long> { 2 }).Concat(primes).ToList(); // Because of how I start it off, I'll just add 2 here
    }

Benchmarks:

• ProgressiveSieve(100,000): 10ms
• ProgressiveSieve(100,000,000): 75102ms

Is there any room for improvement? I feel like finding the square root takes a good bit of time. More importantly, though, is the code compiling down to the most efficient IL? Are there ways I could do the exact same thing faster with optimized C#?

Answer 1

This is my 2nd answer to your post. The first answer focused on comparing it to the Sieve of Eratosthenes. This answer will ignore Eratosthenes and just focus on your method in its own right: the coding style, what’s good, what’s bad, and areas for improvement.

First the Good News

Your use of braces is good and overall spacing is pleasant. The indentation is a bit off, though.

Your casing is good as well.

Areas of Improvement

The worst thing the method does is create 2 lists, which adversely affects memory and performance. There is a simple work around to this below. Fixing this can speed things up 3X.

While i and j are iteration variables, they really could have a more meaningful name. It’s not like i or j are indices into an array or list. I would rename i to number and I would possibly rename j to prime … that is if I keep the foreach (which I don’t).

You could also use var where the type is clearly obvious from a simple assignment statement. This is optional for many, since some violently oppose the var.

You also have no error checking, so someone could input a bound of -1.

Method Signature

I always insist on an access modifier. Anytime I see a method without one, I immediately assume a junior developer forget it, and I’m then prone to wonder what else they may have forgotten.

As mentioned in my 1st answer, you probably should stick with a domain of just int.

It seems obvious that the return type should be List<int> but while internally the primes will be a List<int>, the method could equally return an IList<int>.

public static IList<int> ProgressiveSieve(int bound)
{
    if (bound < 2 || bound > int.MaxValue - 2)
    {
        throw new ArgumentException(nameof(bound));
    }

    var primes = new List<int>() { 2, 3 }; // start it with 2 & 3

    for (var number = 5; number < bound; number += 2) // ignore even values, because they will never be prime except 2
    {
        var isprime = true;
        var sqrt = (int)Math.Sqrt(number);

        for (var j = 1; j < primes.Count && primes[j] <= sqrt; j++)
        {
            if (number % primes[j] == 0) // i is evenly divisible, no need to continue checking
            {
                isprime = false;
                break;
            }
        }

        if (isprime)
        {
            primes.Add(number);
        }
    }

    return primes;
}

Caution Near int.MaxValue

I check that bound is not too large at the top of the method. That why I’m not worried about number += 2 wrapping around to negatives.

One alternative would be to add an extra check in the for:

for (var number = 5; number < bound && number > 3; number += 2)

But this extra check will degrade performance somewhat.

Another alternative would be to have number be a long (but bound remains an int). This only helps at the very high end of int, and may impact performance as well.

The whole caution is to ask yourself what happens if someone puts in a MaxValue for a number type? What steps will you take to deal with that?

That said, Eratosthenes is still faster.

Answer 2

To the contrary, your ProgressiveSieve is slower than decent Sieve of Eratosthenes. I will expand upon the why’s, which also touch on to some points made by @Dmitry. I have seen many implementations here (and written several myself); some may be memory bloated, or code inefficient, but I have never seen one that lets semiprimes slip through.

What is the Sieve’s Domain?

As Dmitry said, you use a long in your method when you’ve only passed an int in your examples. If you bound is never more than int.MaxValue, then your domain is int. This is faster and uses less memory than working with long.

You could step up to uint. It’s still a 32 bit value but it has twice as many primes for a bound of uint.MaxValue. You may hit memory limitations especially since your original method requires 2 lists (thanks to the return statement at the bottom).

So you really should ask yourself what the maximum value you are concerned with, and use the type that is most efficient. Keep in mind that if you want huge numbers, that memory becomes a concern.

A Tale of Two Methodologies

In a nutshell, ProgressiveSieve loops over all odd numbers greater than 3 and checks if the current odd number is divisible by the current known list of primes, up to the sqrt.

The classical sieve of Eratosthenes implementation is to have a list of flags denoting whether an index is prime or composite. The classical approach is to loop over every odd number starting at 3 up to the square root of bound. If the current flag is composite, continue to the top of the loop. If the current flag is prime, output that prime and then mark off multiples as composite.

Some implementations use true for a prime flag; others use true for composite flag. Some use a bool[] which is faster but a memory hog; others use a BitArray which is slower but memory efficient.

Dmitry’s answer includes a beginner’s solution to the classical approach. The flags are stored in a bool[] where a composite flag is true and primes are false. Flags for even and odd numbers are included. This requires 2 collections: the flags bool[] and the output primes List. This also throws an exception for bound equal to int.MaxValue. Plus it is memory intensive but for your example of 100,000,000 this should not be a problem.

My Sieve31 is an optimized approach, though @EBrown’s answer is worth a look. I use a memory efficient BitArray to keep track of only the odd flags beginning at 3. So Sieve31 won’t throw an exception for int.MaxValue. The flags use prime equal to true and composite equal to false. I do not use 2 collections, though someone is free to use .ToList() outside the method.

Comparing the Iterations

Keep this in mind: addition is faster than multiplication which is faster than division. I don’t know where modulo falls in there, but I’m sure it’s slower than addition.

Using a bound of 100 million, or what I call an upperLimit, let’s see how many things are going on inside the sieves.

ProgressiveSieve will loop over odd numbers starting at 5 up to 99,999,999. That means iterating through the main loop 49,999,998 times, and each time through the loop requires a Math.Sqrt. You will iterate over the inner loop 1,931,722,630 times. You will hit the modulo operator 1,925,961,177 times.

Sieve31 calls Math.Sqrt once. It iterates over the first loop a mere 4999 times. Of those, 1228 times it will be a prime and thus calculate the actual number before hitting the inner loop. The inner loop will have 96,285,414 iterations. The final loop will have 49,995,000 iterations.

So Eratosthenes uses less iterations, and less intense operations.

Comparing the Memory

Again for a bound of 100 million:

ProgressiveSieve used 110 MB until it gets to the return statement and needs an additional 115 MB. This was viewed in VS 2015 Debugger. The last .ToList() is also a performance drain.

Sieve31 uses 1 MB of memory, thanks to the BitArray. If I were to use a bool[], this would increase the memory 6X, so 6 MB. But the only collection kept is a set of flags, since the output is an IEnumerable<int>. If one was to use a .ToList(), an additional 21 MB is needed.

So Eratosthenes uses less memory.

Links with Discussions

Sieve31 is a simple solution using a BitArray. However, @EBrown’s answer uses a bool[] for faster results. See the comments to his answer. You may want to review my code and his code, as well as read my post.

Sieve32 bumps it up to a uint. You may want to read the post regarding memory usage, though you don’t have to look at the code.

Sieve32Fast uses parallel threads. I do NOT recommend you look at the code, but there is good text explaining BitArray, performance and memory usage that is worth reading.

Sieve32FastV2 is a code improvement over the above but doesn’t have any of the explanatory text.

Answer 3

First of all, there is the List<T>.Insert method. You can replace

return (new List<long> { 2 }).Concat(primes).ToList();

with the following two lines:

primes.Insert(0, 2);
return primes;

---

Do you really need long data type? The 100,000,000 value perfectly fits into int.
Replacing long with int should speed up your method.

---

I've tried the classical Sieve of Erastosthenes and it seems to be much faster than your approach.
Please try the following method:

private static List<int> Sieve(int bound)
{
    bool[] a = new bool[bound + 1];

    for (int i = 2; i <= Math.Sqrt(bound); i++)
    {
        if (!a[i])
        {
            for (int j = i * i; j <= bound; j += i)
            {
                a[j] = true;
            }
        }
    }

    List<int> primes = new List<int>();
    for (int i = 2; i < a.Length; i++)
    {
        if (!a[i])
        {
            primes.Add(i);
        }
    }

    return primes;
}

Please see Wikipedia for details.
You can also use the BitArray class instead of bool[] to decrease memory consumption.