A prime numbers enumeration optimized for speed

Question

I know there is this thing called "Eratosthenes" but that requires the allocation of a large array while I want to find (small) prime numbers fast, yet without needing too much memory. So I wrote PrimeTable.cs with this content:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Primes
{
    public static class PrimeTable
    {
        private static readonly List<long> PrimeNumbers = new List<long>();

        public static long MaxValue { get; private set; } = 1;

        public static bool IsPrime(this long value)
        {
            if (value > MaxValue) { var longCount = Primes(true).TakeWhile(p => p <= value).LongCount(); }
            return PrimeNumbers.Contains(value);
        }

        public static long IndexOfPrime(this long value) => IsPrime(value) ? Primes().TakeWhile(p => p < value).LongCount() : -1;
        public static long NextPrime(this long value) => Primes().First(p => p > value);
        public static long PreviousPrime(this long value) => Primes().TakeWhile(p => p < value).LastOrDefault();

        public static IEnumerable<long> Primes(bool skipLast = false)
        {
            if (!skipLast) foreach (var l in PrimeNumbers) { yield return l; }
            while (MaxValue < long.MaxValue)
            {
                var max = (int)Math.Sqrt(++MaxValue);
                if (PrimeNumbers.Where(p => p <= max).All(p => MaxValue % p != 0))
                {
                    PrimeNumbers.Add(MaxValue);
                    yield return MaxValue;
                }
            }
        }
    }
}

The reason for this is because I want to stop looking after a certain value has been found. This is mere practice of my skills in enumerations and extension methods and I'm trying to be a bit creative.

So when I ask 11L.IsPrime() it will be true while 99L.IsPrime() will be false. But it won't calculate prime numbers over 11 until I ask if 99L is a prime. Then it won't go past 99. This keeps the number of calculations to a minimum.

The Primes() method is an enumerator that will basically continue calculating nearly forever and would thus take a while if I wasn't using deferred execution. But because of deferred execution, I can just stop enumerating at any moment and later continue the enumeration as it already knows the values it has had.

The IsPrime() is what I want to use in general, to check if a number is a prime or not. To do so, it needs to make sure it has calculated all primes up to the given number and if not, just calculate the remaining primes. It skips the primes it already knows but I have to find a better way to aggregate the enumeration as without the LongCount() in the end, it won't enumerate. It's deferred execution, after all. So, is there a better way to aggregate here?
I can't just use return Primes().Contains(value); as it would run almost forever when checking 99L.

The IndexOfPrime() will tell me the index of a prime number or -1 if it's not a prime.

The NextPrime() method is interesting, though. It will tell me the first prime number after a given value.
The PreviousPrime() method is trickier as I can't just ask for the last item less than value. It would enumerate nearly forever again.

The MaxValue field is just for debugging purposes so you can asl how far it has goine while enumerating...

The next challenge: can this be improved by using PLinq? If so, how?

Answer 1

There are many, many problems with this implementation, but they pretty much all come down to two major problems: first, you do a linear-time operation when a constant-time or log-time operation would suffice, and second, your code is chock-full of expressions that are useful for both their values and their side effects, which makes for code that is confusing.

return PrimeNumbers.Contains(value);

PrimeNumbers is a sorted list, but you check to see if a value is in it by starting from the beginning and searching every element in it. Do a binary search.

public static long IndexOfPrime(this long value) => 
  IsPrime(value) ? Primes().TakeWhile(p => p < value).LongCount() : -1;

This is bizarre. You use IsPrime for its side effect, and then do a linear search of the primes in a list to get their index. You have a list. Just search the list for the index!

This was a good attempt but it has turned into an object lesson in what not to do. The fundamental strategy here is very sound and you should keep it, but the details around that strategy are confusing and inefficient. This is not a good use of LINQ.

What I would do here is refactor the program so that it does a smaller number of things and does them better. For example, suppose instead of this business of constantly enumerating Primes, you instead made two methods:

• EnsureUpTo(n) -- makes sure that the list is filled in up to n.
• NearestIndexOf(n) -- uses an efficient search to return the index of n, or, if n is not prime, the index of the nearest prime to n.
• Prime(i) returns the ith prime.

From this simple interface you can answer all your questions:

• You can determine if n is a prime by running EnsureUpTo(n) and then i = NearestIndex(n) and then m = Prime(i). If n == m then n is prime, otherwise it is composite.

• You can get the next or previous prime similarly; run i = NearestIndex(n) and then Prime(i-1) and Prime(i+1) are the next and previous.

---

Your routine for computing primes you don't already know also could use some work:

  var max = (int)Math.Sqrt(++MaxValue);

A number of problems here. Computing square roots is expensive; it is always better to do p * p <= m than p <= Sqrt(m).

The increment is also suspicious. Fully half the time you will be incrementing it to an even number! After you are at 3, increment it by 2. Or, even better, notice that once you are above 5, you can pick any six numbers in order and at most two of them will be prime. That is, of 5, 6, 7, 8, 9 and 10 we know that 6, 8 and 10 are divisible by 2. We know that 6 and 9 are divisible by 3, so we only need to check 5 and 7. But that also goes for 11, 12, 13, 14, 15, 16: 12, 14, 15 and 16 cannot be prime, so we only have to check 11 and 13. And then 17, 18, 19, 20, 21, 22 we only check 17 and 19. And so on.

So what you can do is increment MaxValue by 6 every time after you get to 5, and then check MaxValue and MaxValue + 2 for primality, and you do much less work.

if (PrimeNumbers.Where(p => p <= max).All(p => MaxValue % p != 0))

Again, this is really bad because LINQ does not know that the list is sorted. You check the entire list, which is O(n) in the size of the list, for elements smaller than max, but you could be bailing out once you get to the first that is larger than max. Where is not the right sequence operator here. You want Until(p => p > max).

Answer 2

I have never seen a post proclaiming “optimized for speed” that uses so much LINQ enumeration. There might be a good reason for that. Don’t get me wrong. I like LINQ. It has nice syntactic sugar but is not known for being highly performant.

I have run some performance tests with your code, so let’s understand my test machine: CPU is an Intel I7-6700 with 4 cores/8 logical processors at 3.40 Ghz, 16GB RAM, .NET Framework 4.8, and Visual Studio 2019. What happens when I run:

var number = 10_000_000;

var sw = new Stopwatch();
var flag = PrimeTable.IsPrime(number);
sw.Stop();

Console.WriteLine($"Number: {number}, IsPrime: {flag}, Elapsed: {sw.Elapsed}");

Your code, supposedly “optimized for speed” returns:

Number: 10000000, IsPrime: False, Elapsed: 00:14:50.8241307

ALMOST 15 MINUTES?! Which makes me wonder: did you even test your own code? If you did not bother, but rather just felt in your mind that it should be fast, then SHAME ON YOU. But if you did performance tests, and walked away thinking it was fast, then SHAME ON YOU 1000 TIMES.

The biggest disconnect I see with your code come from your first sentence, which ends with

I want to find (small) prime numbers fast, yet without needing too much memory.

You never bother to define small. Is it 1000, 100_000, or 1 million? What is small in your mind? You never define it and yet you then use (A) performance dragging LINQ enumerations, and (B) memory consuming List for the PrimeTable both of which are in conflict with your stated objectives.

(As an aside, if you want something small, one can use a very fast, small sieve of Eratosthenes, say of with an upper limit of 1 or 10 million. On my machine, it took a sieve 0.13 seconds (not 15 minutes) to generate the sieve for 10 million and return a fully populated list of primes. That is small, fast, and uses limited memory. The downside is that is does not grow. I am pondering making a sieve that can expand on-demand but that’s a topic for another day.)

When working with sets of primes, generally there are 2 ways to proceed. Either you keep a table of the known primes, or you keep a table of all numbers (usually only the odds) with a flag to denote prime or not. Both come with their own set of advantages and disadvantages. After you weigh your objectives over the advantages/disadvantages, you then pick your poison, and should try to provide a practical solution. You chose a prime table.

Your PrimeTable seems to be unbounded, other than it would be limited by Int64.MaxValue. Except it’s really constrained earlier in that the index to PrimeTable is limited to Int32.MaxValue. On a more practical level, you are limited further in .NET’s memory usage. On my machine, I can have List<Int64> of 134_217_728 primes before throwing a memory error. Consider further:

For 31 bit primes, that is all of Int32, there will be 105_097_565 primes and the last known prime is 2_147_483_647. For 32 bit primes, that is all of UInt32, there will be 203_280_221 primes and the last known prime is 4_294_967_291. I got this from using a sieve. Granted it takes less than 45 seconds to generate the entire sieve, which you may scoff at, but then again it took 15 minutes for yours to tell me that 10 million is not a prime.

If you defined your PrimeTable to be a List<UInt32>, you could hold all 203_280_221 primes in memory. Granted it may take months for your app to find them all.

On to other topics, I don’t like the static property named MaxValue. There is no written standard, but generally when I see a property named MaxValue, I tend to think of it as a value that never changes. You state that it’s only for debugging, but some very critical logic for producing primes depends on it.

Suggestions for improvement

Follow Eric Lippert's advice to use an efficient search instead of performance killing LINQ enumerations.

I would suggest starting out practical with Int32 instead of Int64. However, since I am working with your current code, I am using long below.

At the very least, I would initialize PrimeTable to be:

private static readonly List<long> PrimeNumbers = new List<long>() { 2 };

But why stop there? Why not start it with:

private static readonly List<long> PrimeNumbers = new List<long>() { 2, 3, 5, 7, 11, 13, 17, 19 };

Once you do that, you can add 2 very nice properties:

public static int KnownPrimeCount => PrimeNumbers.Count;
public static long LargestKnownPrime => PrimeNumbers.Last();

And maybe LargestKnownPrime can make MaxValue go away.

Another suggestion is that since you have a list in memory, why not expose that to the user? Perhaps:

public static IReadOnlyList<long> KnownPrimes => PrimeNumbers;

IsPrime – Horrible Implementation

As shown above, it took almost 15 minutes to determine that 10 million is not a prime. Let’s start out with a couple of quick improvements for the very top of IsPrime:

if (value < 2) { return false; }
if (value % 2 == 0) { return value == 2; }

The performance still is bad if I were to use 10_000_001. The problem is that checking an individual number for primality is a very different task than generating a list of a whole bunch of primes. There is no need to use to PrimeTable just to determine primality, but since you have it, you could use it. But I would use it as-is and not try to grow the table.

public static bool IsPrime(this long value)
{
    if (value < 2) { return false; }
    if (value % 2 == 0) { return value == 2; }
    if (value <= LargestKnownPrime)
    {
        // determine using fast lookup to PrimeTable
        return from_table_via_fast_lookup;
    }
    // compute without modifying PrimeTable
    // https://codereview.stackexchange.com/questions/196196/get-prime-divisors-of-an-int32-using-a-wheel
    // https://codereview.stackexchange.com/questions/92575/optimized-ulong-prime-test-using-6k-1-in-parallel-threads-with-c
    return something;
}

Answer 3

I was hoping to see you come out with an improved Version 2 with a new posting. I began to write some code for an answer to you, but that code diverged so much from your original that it warrants being its own post for review:

Prime Number Table, i.e. List<int>

This is similar to yours, was inspired by yours, but eventually has different goals and objectives than yours. A least one goal we have in common is a desire to provide a many primes quickly to a consumer.

I do use a faster lookup to index, which was highly recommended to you.

I also expose the table to the consumer as a readonly list. For all the time, energy, and memory you use to build this table, I see no reason to hide it away.

My implementation doesn't carry the same side effects as yours, but again this is a design decision (our different goals) in that I restrict any methods using the index to the known primes, i.e. those already in my table. I do not look past or add to the known primes on many calls.

Where we absolutely differ is that I use a sieve to initialize my prime table. For most responsiveness in an app, I use time rather than prime count as the driving factor. The sieve is temporary, creates the prime table, and its memory returned to later be GC'ed. And it is much, much faster than generating primes using naive methods.

You take some issue with sieves due to allocation. I would ask you to instead look at it with an open mind and an opportunity to learn new things.

Let's compare the memory used by a sieve versus a List<int> along with an upperLimit of 10 million. There are 664_579 primes in that list. This requires 2_658_316 bytes.

If one use a bool[] and only used odd numbers, the array would need 5_000_001 items, and each item is a byte. This is almost twice the size of the List<int>.

However, I do not use a bool[] but instead use a Systems.Collection.BitArray. Here each odd number is only 1 bit. Note the underlying values in a bit array are provided by an int, where a single int provides 32 bits. Thus my BitArray of 5_000_001 bits requires 156_282 integers, or 625_128 bytes. Thus my BitArray is 0.25 the size of the List<int>.

So I can prove that sieve is much faster than your naive methods, and a sieve with a BitArray uses less memory than a `List'.

I would encourage to try an improved implementation of your own and would welcome a chance to see and review it.