A prime numbers enumeration optimized for speed
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).