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?
true
orfalse
at specific positions. \$\endgroup\$Long.MaxValue
? According to WolframAlpha there are about 2.11214×10^17 primes under this value, which would take 1.6897×10^9 GB of RAM to storelong
, where you'd need 1.153×10^9 GB for the equivalent sieve. Maybe you didn't implement the sieve correctly? \$\endgroup\$PrimeNumbers.Where(p => p <= max).All(p => MaxValue % p != 0)
, again well before you hit Int32.MaxValue. \$\endgroup\$UInt32
primes in about 40 seconds and use under 300 MB memory. \$\endgroup\$