我如何测试素数？

Question

我正在写一个带有一些质数相关方法的小库。因为我已经做了基础工作(也就是工作方法)，现在我正在寻找一些优化。当然，互联网是一个很好的这样做的地方。然而，我偶然发现了一个舍入问题，我想知道如何解决这个问题。

在我用来测试一个数的质数的循环中，搜索到sqrt(n)比n/2甚至n- 1更有效，但是由于舍入问题，一些数字被跳过了，因此一些质数被跳过了！例如，第10000个素数应该是: 104729，但“优化”版本的结尾是: 103811。

一些代码(我知道它是为更多优化而开放的，但我一次只能处理一件事)：

/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
    // 0 and 1 are not prime numbers
    if (test == 0 || test == 1) return false;

    // 2 and 3 are prime numbers
    if (test == 2) return true;

    // all even numbers, save 2, are not prime
    if (test % 2 == 0) return false;

    double squared = Math.Sqrt(test);
    int flooredAndSquared = Convert.ToInt32(Math.Floor(squared));

    // start with 5, make increments of 2, even numbers do not need to be tested
    for (int idx = 3; idx < flooredAndSquared; idx++)
    {
        if (test % idx == 0)
        {
            return false;
        }
    }
    return true;
}

我知道平方部分失败了(或者我失败了)，也尝试了Math.Ceiling，得到了大致相同的结果。

Answer 1

遗憾的是，我以前没有尝试过算法方法。但是如果你想高效地实现你的方法，我建议你做一些缓存。创建一个数组来存储小于定义阈值的所有质数，填充此数组，并在其中进行搜索。

在下面的示例中，在最好的情况下(即，当数字小于或等于maxPrime时，64K缓冲区为821,461 )，确定一个数字是否为质数是O(1)，并且针对其他情况进行了一定程度的优化(通过仅检查前820,000个数字中的64K个数字的mod --大约8%)。

(注意:不要将此答案视为“最佳”方法。它更像是一个关于如何优化您的实现的示例。)

public static class PrimeChecker
{
    private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB

    private static int[] primes;
    public static int MaxPrime { get; private set; }

    public static bool IsPrime(int value)
    {
        if (value <= MaxPrime)
        {
            return Array.BinarySearch(primes, value) >= 0;
        }
        else
        {
            return IsPrime(value, primes.Length) && IsLargerPrime(value);
        }
    }

    static PrimeChecker()
    {
        primes = new int[BufferSize];
        primes[0] = 2;
        for (int i = 1, x = 3; i < primes.Length; x += 2)
        {
            if (IsPrime(x, i))
                primes[i++] = x;
        }
        MaxPrime = primes[primes.Length - 1];
    }

    private static bool IsPrime(int value, int primesLength)
    {
        for (int i = 0; i < primesLength; ++i)
        {
            if (value % primes[i] == 0)
                return false;
        }
        return true;
    }

    private static bool IsLargerPrime(int value)
    {
        int max = (int)Math.Sqrt(value);
        for (int i = MaxPrime + 2; i <= max; i += 2)
        {
            if (value % i == 0)
                return false;
        }
        return true;
    }
}

Answer 2

我想这就是你的问题：

for (int idx = 3; idx < flooredAndSquared; idx++)

这应该是

for (int idx = 3; idx <= flooredAndSquared; idx++)

所以你不会得到平方数作为素数。此外，您可以使用"idx += 2“而不是"idx++”，因为您只需测试奇数(正如您在上面的注释中所写的那样...)。

Answer 3

我不知道这是不是你正在寻找的东西，但如果你真的关心速度，那么你应该研究测试素数的概率方法，而不是使用筛子。Rabin-Miller是Mathematica使用的一种概率素数测试。