Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
PrimeFactory class (with caching). Required by Factorization class.
public static class PrimeFactory
{
private static BigInteger _cacheLargestPrimeCurrently;
private static BigInteger _cacheCeiling;
internal static BigInteger[] _primeCache;
static PrimeFactory()
{
_cacheCeiling = BigInteger.Pow(11, 7);
_primeCache = new BigInteger[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
_cacheLargestPrimeCurrently = _primeCache.Last();
}
public static void EnsurePrimeCacheSize(BigInteger maxPrime)
{
BigInteger boundedPrimeRequest = BigInteger.Min(maxPrime, _cacheCeiling);
if (_cacheLargestPrimeCurrently < boundedPrimeRequest)
{
_primeCache = PrimeFactory.GetPrimes(boundedPrimeRequest).ToArray();
_cacheLargestPrimeCurrently = _primeCache.Last();
}
}
public static bool IsPrime(BigInteger p)
{
var absP = BigInteger.Abs(p);
EnsurePrimeCacheSize(absP + 1);
return _primeCache.Contains(absP);
}
public static int GetIndexFromValue(int value)
{
if (value == -1)
{
return -1;
}
EnsurePrimeCacheSize(value + 1);
BigInteger primeValue = _primeCache.First(p => p >= value);
int index = Array.IndexOf(_primeCache, primeValue);
return index;
}
public static BigInteger GetValueFromIndex(int index)
{
while (!_primeCache.Any() || (_primeCache.Length - 1) < index)
{
EnsurePrimeCacheSize(GetApproximateNthPrime(index) + 1);
}
BigInteger value = _primeCache[index];
return value;
}
public static int GetApproximateNthPrime(int n)
{
// n*ln( n*e*ln(ln(n)) )
double approx = n * Math.Log(n * Math.E * Math.Log(Math.Log(n)));
double ceil = Math.Ceiling(approx);
return (int)ceil;
}
public static List<BigInteger> GetPrimes(BigInteger ceiling)
{
return GetPrimes(2, ceiling);
}
public static List<BigInteger> GetPrimes(BigInteger floor, BigInteger ceiling)
{
if (floor < 2)
{
floor = 2;
}
if (floor > ceiling)
{
throw new ArgumentOutOfRangeException("floor > ceiling");
}
if (ceiling < 10)
{
if (ceiling == 9 || ceiling == 8 || ceiling == 7)
{
return new List<BigInteger>() { 2, 3, 5, 7 };
}
else if (ceiling == 6 || ceiling == 5)
{
return new List<BigInteger>() { 2, 3, 5 };
}
else if (ceiling == 4 || ceiling == 3)
{
return new List<BigInteger>() { 2, 3 };
}
else
{
return new List<BigInteger>() { 2 };
}
}
if (_primeCache.Length > 0 && _primeCache.Last() >= ceiling)
{
return _primeCache.SkipWhile(i => floor > i).TakeWhile(i => ceiling >= i).ToList();
}
BigInteger counter = 0;
BigInteger counterStart = 3;
BigInteger inc;
BigInteger sqrt = 3;
BigInteger ceil = ceiling > Int32.MaxValue ? Int32.MaxValue - 2 : ceiling;
bool[] primeMembershipArray = new bool[(int)ceil + 1];
primeMembershipArray[2] = true;
// Set all odds as true
for (counter = counterStart; counter <= ceiling; counter += 2)
{
if ((counter & 1) == 1) // Check if odd
{
primeMembershipArray[(int)counter] = true;
}
}
while (sqrt * sqrt <= ceiling)
{
counter = sqrt * sqrt;
inc = sqrt + sqrt;
while (counter <= ceiling)
{
primeMembershipArray[(int)counter] = false;
counter += inc;
}
sqrt += 2;
while (!primeMembershipArray[(int)sqrt])
{
sqrt++;
}
}
var maxRange = ceiling.SquareRoot();
IEnumerable<BigInteger> primesCollection = Maths.GetRange(2, ceiling - 1).Where(n => primeMembershipArray[(int)(n)] == true).ToList();
if (primesCollection.Count() > _primeCache.Count())
{
_primeCache = primesCollection.ToArray();
}
List<BigInteger> result = primesCollection.Where(l => l >= floor && l <= ceiling).ToList();
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment