我该如何测试素性？

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

我猜这是你的问题:

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

这应该是

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

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

Answer 2

我不知道这是否是您正在寻找的,但如果您真的关心速度,那么您应该研究一下测试素质而不是使用筛子的可能方法.Rabin-Miller是Mathematica使用的概率素性测试.

Answer 3

可悲的是,我之前没有尝试过算法.但是如果你想有效地实现你的方法,我建议做一些缓存.创建一个数组来存储小于定义阈值的所有素数,填充此数组,然后在其中搜索/使用它.

在下面的示例中,查找数字是否为素数在最佳情况下是O(1)(即,当数字小于或等于maxPrime,对于64K缓冲区为821,461),并且在某种程度上针对其他情况进行了优化(通过检查第一个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 4

我发布了一个使用筛子或Eratosthenes来计算质数的类:

数组的大小是否受int的上限(2147483647)约束？