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
You could step up to
uint. It’s still a 32 bit value but it has twice as many primes for a
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
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.
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.
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.
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.