c# - 使用 BigInteger 的阿特金筛法的质数

Question

有人知道使用 BigInteger 的 C# 阿特金筛算法吗？据我了解，这是目前最著名的素因数分解算法。

我目前有这个功能:

/// <summary>
        /// Finds prime numbers using the Sieve of Atkins algorithm.
        /// </summary>
        /// <param name="max">The limit of the prime list.</param>
        /// <returns>The list of prime numbers.</returns>
        public List<int> FindPrimes(int max)
        {
            var isPrime = new bool[max + 1];
            var sqrt = (int) Math.Sqrt(max);

            Parallel.For(1, sqrt, x =>
            {
                var xx = x * x;
                for (int y = 1; y <= sqrt; y++)
                {
                    var yy = y * y;
                    var n = 4 * xx + yy;
                    if (n <= max && (n % 12 == 1 || n % 12 == 5))
                        isPrime[n] ^= true;

                    n = 3 * xx + yy;
                    if (n <= max && n % 12 == 7)
                        isPrime[n] ^= true;

                    n = 3 * xx - yy;
                    if (x > y && n <= max && n % 12 == 11)
                        isPrime[n] ^= true;
                }
            });

            var primes = new List<int>() { 2, 3 };
            for (int n = 5; n <= sqrt; n++)
            {
                if (isPrime[n])
                {
                    primes.Add(n);
                    int nn = n * n;
                    for (int k = nn; k <= max; k += nn)
                        isPrime[k] = false;
                }
            }

            for (int n = sqrt + 1; n <= max; n++)
                if (isPrime[n])
                    primes.Add(n);

            return primes;

        }

但我想要一个看起来更像下面的函数签名，这样它就可以接受单个数字来测试并输出 true(如果该数字是质数)。

public bool IsPrime(BigInteger number) { ... }

Answer 1

您应该以不同的方式解决几个相关的问题:

• 查找给定合数的所有素因数:根据大小，您应该使用 Pollard rho、椭圆曲线法、二次筛或数域筛来实现此目的。一般来说，对数字进行因式分解需要很长时间。
• 测试给定数字是否为质数:您应该使用 Miller-Rabin 来实现此目的。它的速度非常快，并且通过使用素数的特征而不是“没有非平凡因数的素数”来规避“分解数字很慢”的问题。
• 查找某个范围内的所有素数:对于接近零的范围使用埃拉托色尼筛，对于远离零的范围使用阿特金筛。

您询问如何应用阿特金筛来测试素数或将数字分解为素数。这是解决这两个问题的错误方法。