Prime Factorization class.

Factorization.cs

using System.Numerics;

public static class Factorization
{
    private static BigInteger _cacheCeiling;
    private static List<BigInteger> _primeCache;
    private static BigInteger _cacheLargestPrimeCurrently;
    private static BigInteger[] _probablePrimeCheckBases;

    static Factorization()
    {
        _cacheCeiling = BigInteger.Pow(11, 8);
        _primeCache = new List<BigInteger> { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
        _probablePrimeCheckBases = _primeCache.ToArray();
        _cacheLargestPrimeCurrently = _primeCache.Last();
    }

    public static void EnsurePrimeCacheSize(BigInteger maxPrime)
    {
        BigInteger boundedPrimeRequest = BigInteger.Min(maxPrime, _cacheCeiling);
        if (_cacheLargestPrimeCurrently < boundedPrimeRequest)
        {
            _primeCache = FastPrimeSieve.GetRange(2, boundedPrimeRequest);
            _cacheLargestPrimeCurrently = boundedPrimeRequest;
        }
    }

    public static IEnumerable<BigInteger> GetPrimeFactorization(BigInteger value, BigInteger maxValue)
    {
        value = BigInteger.Abs(value);
        maxValue = BigInteger.Min(maxValue, value.SquareRoot() + 1);

        if (value == 0) { return new BigInteger[] { 0 }; }
        if (value < 10) { if (value == 0 || value == 1 || value == 2 || value == 3 || value == 5 || value == 7) { return new List<BigInteger>() { value }; } }

        BigInteger primeListSize = maxValue + 5;

        EnsurePrimeCacheSize(primeListSize);

        if (_primeCache.Contains(value)) { return new List<BigInteger>() { value }; }

        List<BigInteger> factors = new List<BigInteger>();
        foreach (BigInteger prime in _primeCache)
        {
            while (value % prime == 0)
            {
                value /= prime;
                factors.Add(prime);
            }

            if (value == 1) break;
        }

        if (value != 1) { factors.Add(value); }

        return factors;
    }

    // Essentially Miller-Rabin probabilistic primality test, with caching
    public static bool IsProbablePrime(BigInteger input)
    {
        if (input == 2 || input == 3)
        {
            return true;
        }
        if (input < 2 || input % 2 == 0)
        {
            return false;
        }

        EnsurePrimeCacheSize(input + 1);

        if (input < _cacheLargestPrimeCurrently)
        {
            return _primeCache.Contains(input);
        }

        BigInteger d = input - 1;
        int s = 0;

        while (d % 2 == 0)
        {
            d >>= 1;
            s += 1;
        }

        foreach (BigInteger a in _probablePrimeCheckBases)
        {
            BigInteger x = BigInteger.ModPow(a, d, input);
            if (x == 1 || x == input - 1)
            {
                continue;
            }

            for (int r = 1; r < s; r++)
            {
                x = BigInteger.ModPow(x, 2, input);
                if (x == 1)
                {
                    return false;
                }
                if (x == input - 1)
                {
                    break;
                }
            }

            if (x != input - 1)
            {
                return false;
            }
        }
        return true;
    }

    public static BigInteger GetNextPrime(BigInteger fromValue)
    {
        BigInteger result = fromValue + 1;
        if (result.IsEven)
        {
            result += 1;
        }

        while (!Factorization.IsProbablePrime(result))
        {
            result += 2;
        }

        return result;
    }

    public static BigInteger GetPreviousPrime(BigInteger fromValue)
    {
        BigInteger result = fromValue.IsEven ? fromValue - 1 : fromValue - 2;

        while (result > 0)
        {
            if (Factorization.IsProbablePrime(result))
            {
                return result;
            }
            result -= 2;
        }

        throw new Exception($"No primes exist between {fromValue} and zero.");
    }
}

FastPrimeSieve.cs

using System.Numerics;
using System.Management;

public class FastPrimeSieve : IEnumerable<BigInteger>
{
    private static readonly uint PageSize; // L1 CPU cache size in bytes
    private static readonly uint BufferBits;
    private static readonly uint BufferBitsNext;

    static FastPrimeSieve()
    {
        uint cacheSize = 393216;
        List<uint> cacheSizes = CPUInfo.GetCacheSizes(CPUInfo.CacheLevel.Level1);
        if (cacheSizes.Any())
        {
            cacheSize = cacheSizes.First() * 1024;
        }

        PageSize = cacheSize; // L1 CPU cache size in bytes
        BufferBits = PageSize * 8; // in bits
        BufferBitsNext = BufferBits * 2;
    }

    public static IEnumerable<BigInteger> GetRange(BigInteger floor, BigInteger ceiling)
    {
        FastPrimeSieve primesPaged = new FastPrimeSieve();
        IEnumerator<BigInteger> enumerator = primesPaged.GetEnumerator();

        while (enumerator.MoveNext())
        {
            if (enumerator.Current >= floor)
            {
                break;
            }
        }

        do
        {
            if (enumerator.Current > ceiling)
            {
                break;
            }
            yield return enumerator.Current;
        }
        while (enumerator.MoveNext());

        yield break;
    }

    public IEnumerator<BigInteger> GetEnumerator()
    {
        return Iterator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return (IEnumerator)GetEnumerator();
    }

    private static IEnumerator<BigInteger> Iterator()
    {
        IEnumerator<BigInteger> basePrimes = null;
        List<uint> basePrimesArray = new List<uint>();
        uint[] cullBuffer = new uint[PageSize / 4]; // 4 byte words

        yield return 2;

        for (var low = (BigInteger)0; ; low += BufferBits)
        {
            for (var bottomItem = 0; ; ++bottomItem)
            {
                if (bottomItem < 1)
                {
                    if (bottomItem < 0)
                    {
                        bottomItem = 0;
                        yield return 2;
                    }

                    BigInteger next = 3 + low + low + BufferBitsNext;
                    if (low <= 0)
                    {
                        // cull very first page
                        for (int i = 0, sqr = 9, p = 3; sqr < next; i++, p += 2, sqr = p * p)
                        {
                            if ((cullBuffer[i >> 5] & (1 << (i & 31))) == 0)
                            {
                                for (int j = (sqr - 3) >> 1; j < BufferBits; j += p)
                                {
                                    cullBuffer[j >> 5] |= 1u << j;
                                }
                            }
                        }
                    }
                    else
                    {
                        // Cull for the rest of the pages
                        Array.Clear(cullBuffer, 0, cullBuffer.Length);

                        if (basePrimesArray.Count == 0)
                        {
                            // Init second base primes stream
                            basePrimes = Iterator();
                            basePrimes.MoveNext();
                            basePrimes.MoveNext();
                            basePrimesArray.Add((uint)basePrimes.Current); // Add 3 to base primes array
                            basePrimes.MoveNext();
                        }

                        // Make sure basePrimesArray contains enough base primes...
                        for (BigInteger p = basePrimesArray[basePrimesArray.Count - 1], square = p * p; square < next;)
                        {
                            p = basePrimes.Current;
                            basePrimes.MoveNext();
                            square = p * p;
                            basePrimesArray.Add((uint)p);
                        }

                        for (int i = 0, limit = basePrimesArray.Count - 1; i < limit; i++)
                        {
                            var p = (BigInteger)basePrimesArray[i];
                            var start = (p * p - 3) >> 1;

                            // adjust start index based on page lower limit...
                            if (start >= low)
                            {
                                start -= low;
                            }
                            else
                            {
                                var r = (low - start) % p;
                                start = (r != 0) ? p - r : 0;
                            }
                            for (var j = (uint)start; j < BufferBits; j += (uint)p)
                            {
                                cullBuffer[j >> 5] |= 1u << ((int)j);
                            }
                        }
                    }
                }

                while (bottomItem < BufferBits && (cullBuffer[bottomItem >> 5] & (1 << (bottomItem & 31))) != 0)
                {
                    ++bottomItem;
                }

                if (bottomItem < BufferBits)
                {
                    var result = 3 + (((BigInteger)bottomItem + low) << 1);
                    yield return result;
                }
                else break; // outer loop for next page segment...
            }
        }
    }
}

public static class CPUInfo
{
    public static List<uint> GetCacheSizes(CacheLevel level)
    {
        ManagementClass mc = new ManagementClass("Win32_CacheMemory");
        ManagementObjectCollection moc = mc.GetInstances();
        List<uint> cacheSizes = new List<uint>(moc.Count);

        cacheSizes.AddRange(moc
          .Cast<ManagementObject>()
          .Where(p => (ushort)(p.Properties["Level"].Value) == (ushort)level)
          .Select(p => (uint)(p.Properties["MaxCacheSize"].Value)));

        return cacheSizes;
    }

    public enum CacheLevel : ushort
    {
        Level1 = 3,
        Level2 = 4,
        Level3 = 5,
    }
}