A prime numbers enumeration optimized for speed 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&lt;long&gt; PrimeNumbers = new List&lt;long&gt;();

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

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

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

        public static IEnumerable&lt;long&gt; Primes(bool skipLast = false)
        {
            if (!skipLast) foreach (var l in PrimeNumbers) { yield return l; }
            while (MaxValue &lt; long.MaxValue)
            {
                var max = (int)Math.Sqrt(++MaxValue);
                if (PrimeNumbers.Where(p =&gt; p &lt;= max).All(p =&gt; 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?
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) =&gt; 
  IsPrime(value) ? Primes().TakeWhile(p =&gt; p &lt; 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 &lt;= m than p &lt;= 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 =&gt; p &lt;= max).All(p =&gt; 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 =&gt; p &gt; max).