使用带有BigInteger的Atkin筛子的质数 [英] Prime numbers using Sieve of Atkin with BigInteger

问题描述

有人碰巧知道使用BigInteger的Atkin算法的C#筛子吗?据我了解，这是目前最著名的素数分解算法.

Does anyone happen to know of a C# Sieve of Atkin algorithm using BigInteger? From my understanding, this is the best known prime factorization algorithm currently in existence.

我目前具有此功能:

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

But I would like to have a function signature that looks more like below so it can take in a single number to test and output true if the number is prime.

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

推荐答案

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

I think, by the nature of the algorithm, there's no direct way to check if N is prime.

要检查N是否为素数，首先可以使用简单的除数(2、5、7等)，然后可以生成N下的所有Atkin素数，然后尝试将N除以每个Atkin素数.如果可以整除，则返回false.如果没有，那么恐怕您将不得不测试N ...下的所有数字.

To check if N is prime, first, you can use the easy divisors (2, 5, 7, etc), then you can generates all the Atkin primes under N, and then try to divide N by each Atkin prime. If it's divisible, then you return false. If not, then I'm afraid you will have to test all the numbers under N....

也许您可以使用一些概率方法，这种方法可以更有效地检查单个数字.尝试使用米勒-拉宾或

Maybe you can use some probabilistic approach, which can be far more efficient to check a single number. Try methods like Miller–Rabin or Solovay–Strassen primality test (used in RSA).

我想您会很高兴:这是 Solovay的实现，并且这是关于所有原始性的非常有趣的页面测试算法.

I think you will be happy : here's an implementation of Solovay, and here's an very interesting page about all the primality testing algorithms.

这篇关于使用带有BigInteger的Atkin筛子的质数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！