使用带有 BigInteger 的阿特金筛法的素数

Question

有没有人碰巧知道使用 BigInteger 的 C# Sieve of Atkin 算法？据我了解，这是目前最著名的质因数分解算法。

我目前有这个功能：

/// <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

我认为，根据算法的性质，没有直接的方法来检查 N 是否为素数。

判断N是否为素数，首先可以使用易除数（2、5、7等），然后生成N以下的所有阿特金素数，然后尝试将N除以每个阿特金素数主要。如果它是可整除的，那么你 return 错误。如果没有，那恐怕你得把N以下的数字都考一遍....

也许你可以使用一些概率方法，它可以更有效地检查单个数字。尝试像 Miller–Rabin or Solovay–Strassen 素数测试（在 RSA 中使用）这样的方法。

我想你会很高兴：here's an implementation of Solovay, and here's 一个关于所有素性测试算法的非常有趣的页面。

Answer 2

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

找出给定合数的所有质因数：根据大小，您应该使用 Pollard rho、椭圆曲线法、二次筛或数域筛。分解数字一般需要很长时间。
测试给定数字是否为质数：为此您应该使用 Miller-Rabin。它非常快，并且通过使用 "those that have no nontrivial factors."
找到一个范围内的所有素数：对接近零的范围使用埃拉托色尼筛法，对远离零的范围使用阿特金筛法。

您问的是关于应用阿特金筛法来检验素数或将一个数分解为素数。这是解决任一问题的错误方法。

使用带有 BigInteger 的阿特金筛法的素数

Prime numbers using Sieve of Atkin with BigInteger

c#

math

primes

prime-factoring