素性测试

• 从本文下载算法 - 1 Kb

介绍 

在本文中，我将向您展示如何优化用于计算数字是否为素数的暴力算法。我将一步一步地、带有证明地展示这是如何完成的。

在编程竞赛中，快速计算素数的需求很普遍，因为速度至关重要。此外，我还会解释一种算法，当我们需要知道一组数字中有哪些是素数时，该算法非常有用且速度快。

本文分为两部分，第一部分介绍如何判断一个特定的数字是否为素数。第二部分介绍如何判断一组数字中有哪些是素数。

我事先声明，本文主要涵盖判断数字是否为素数的方法的数学部分。所以，如果您不擅长数学，可能会感到乏味。

注意 1：示例中将使用 C++ 代码。

注意 2：我们认为 1 不是素数。

第一部分

暴力算法

根据定义，素数是指除了 1 和它本身之外没有正因数的数字。根据这个定义，计算数字“number”是否为素数的最简单方法诞生了。它包括检查从 2 到 number-1 的每个数字，看 number 是否至少被其中一个数字整除。我们将此方法称为 IsPrimeByBruteForce，它接收一个参数，即要评估其素性的数字，并返回一个布尔值，指示是否为素数。

这是 IsPrimeByBruteForce 的代码

bool IsPrimeByBruteForce(int number)
{
    if(number<2)
        return false;
    for(int i=2; i<number; i++)
    {
        //A number "number" is divisible by another number "i"
        //if the rest of the division of number divided i equals to zero
        if(number%i==0)
            return false;
    }
    //If no exist a number between 2 and number-1 that divides number
    return true;
}

现在的问题是：这可以优化吗？

答案是：可以（因为我写这篇文章就是为了这个），而且可以通过不检查从 2 到 number-1 的每个数字是否能整除 number 来实现。这就是我们要介绍的第二种方法。

优化算法

我之前说过，我们可以通过不检查从 2 到 number-1 的每个数字是否能整除 number 来优化 IsPrimeByBruteForce 算法。那么，应该检查哪些数字呢？这个问题的答案是，我们只需要检查从 2 到 number/2 的每个数字是否能整除 number。

证明如下：

如果一个数字“number”不是素数，那么至少存在两个数字（我们称它们为 a 和 b），它们的乘积等于 number。

 (1)

我说过我们需要检查从 2 到 number-1 的每个数字是否能整除 number。所以，如果我们是对的，在上面的等式中，如果“a”大于 number/2，那么“b”必须小于或等于 number/2。那么我们需要证明

如果我们证明了这一点，我们就可以确定，为了证明 number 是否为素数，我们只需要检查从 2 到 number/2 的每个数字。因为（在上述方程中）“a”或“b”必然小于或等于 number/2（如果我们是对的）。

现在假设 a 大于 number/2。即

(2) 

那么，a 至少是 number/2 + 1（因为 number/2 + 1 大于 number/2）。现在，我们假设 a 是 number/2 + 1。

然后我们得到（将 (2) 代入 (1)）：

   

然后我们得到：

(3)   

现在我们需要证明

现在，我们假设：

 (4) 

将 (3) 代入 (4) 并继续求解方程：

这样我们就证明了，如果 number >= 2，那么“a”或“b”小于或等于 number/2。

另外一点需要考虑的是 number/2 的两种可能情况，因为 number 是奇数还是偶数。因为我们程序的除法计算的是除法的向下取整值（例如，5/2 = 2）。

情况 1：如果 number 是偶数，例如 6，那么 number/2 是 3，没有余数，所以我们不用担心这种情况。

情况 2：如果 number 是奇数，例如 5，那么 number/2 是 2，余数为 1。在这种情况下，我们必须证明它的可除性直到 2，因为如果我们乘以 3 * 2（floor(number/2) * 2），结果会大于 number。

因此，我们得出结论，检查可除性直到 floor(number/2) 即可，而这正是计算机所能计算的。

所以，如果我们想检查一个数字是否为素数，我们只需要检查它是否能被从 2 到 floor(number/2) 的每个数字整除。我们将此算法称为“IsPrimeOptimizationOne”，它接收与“IsPrimeByBruteForce”方法相同的参数，并返回相同的类型。我们在下面定义了这个函数：

bool IsPrimeOptimizationOne(int number)
{
    if(number<2)
        return false;
    if(number==2)
        return true;
    for(int i=2;i<=number/2;i++)
    {
        if(number%i==0)
            return false;
    }
    //If no exist a number between 2 and number/2 that divides number
    return true;
}

现在的问题是：上面的方法是否可以进一步优化？答案是肯定的。

我们现在证明，我们只需要检查数字的可除性直到数字的平方根（我们称之为 sqrt(number)）。我们将在下面（以与我们的第一个证明相同的方式）证明这一点。

 (5) 

 (6) 

现在，我们将 b 的值（6）代入我们的不等式 (5)：

这样我们就证明了，对于 number >= 0，我们可以通过只检查从 2 到 sqrt(number) 的每个数字的可除性来证明其素性。

您可能想知道我怎么知道这种方法比第一种方法更好。我们在这里证明了这一点。

 

我们已经证明，如果 number >= 2，那么 number 的平方根小于或等于 number/2。所以，如果我们检查到 sqrt(number)，我们比检查到 number/2 所做的比较要少。此算法与“IsPrimeOptimizationOne”相同，只是检查的上限不同。我们将此算法称为“IsPrimeOptimizationTwo”，它具有与“IsPrimeByBruteForce”和“IsPrimeOptimizationOne”方法相同的参数和返回值。该算法在此定义：‎

bool IsPrimeOptimizationTwo(int number)
{
    if(number<2)
        return false;
    if(number==2)
        return true;
    //sqrt() function is defined in cmath library (#include&ltcmath&gt)
    for(int i=2;i<=sqrt(number);i++)
    {
        if(number%i==0)
            return false;
    }
    //If no exist a number between 2 and number/2 that divides number
    return true;
}

最后一个优化基于一个事实：如果 number 是偶数，那么它不是素数。如果一个数字能被 2 整除，那么它就能被 4、6、8、...、number/2 整除。所以我们只需要检查它是否能被 2 整除，否则我们只需要检查 2*k + 1 形式的数字（即奇数）。因此，在一个基于“IsPrimeOptimizationTwo”的新算法中，我们在 for 循环之前检查 number 是否为偶数。如果是，那么它不是素数。否则，我们检查 number 是否能被 i 整除，从 i=3 开始，直到 sqrt(number)，每次循环 i 增加 2。我们将此算法称为“IsprimeOptimizationThree”，它在此定义：

bool IsPrimeOptimizationThree(int number)
{
    if(number<2)
        return false;
    if(number==2)
        return true;
    if(number%2==0)
        return false;
    for(int i=3;i<=sqrt(number);i += 2)
    {
        if(number%i==0)
            return false;
    }
    return true;
}

以上是我所知道的可以用来判断一个数字是否为素数的所有优化方法。如果您知道其他优化方法，请留言。

第二部分

注意：我收到了许多评论，因为有一个之前的文章介绍了这种方法。如果您想查看，以下是文章链接：Finding prime numbers。我在这里简要提及它，因为它在了解该方法和何时使用它方面很有用。   

之前我们看到了判断一个特定数字是否为素数的算法。但是，如果我们想知道一组数字中的所有素数，我们可以为集合中的每个数字调用“IsPrimeOptimizationThree”函数，但这效率低下，因为我们为每个数字重复相同的除法。例如，如果我们检查集合 {13,14,26}，我们会将这三个数字都除以 2，都除以 3，以此类推。

在这种情况下，最好使用的算法是埃拉托斯特尼筛法。该算法避免了重复的除法。为了解释这个算法，我将使用一张我喜欢的图片，来自维基百科。

注意：下面的所有图片均来自维基百科，具体来说是这篇文章：埃拉托斯特尼筛法。

我们想知道小于或等于 120 的所有素数。首先，所有数字都显示为灰色。

然后我们排除所有 2 的倍数，因为它们不是素数。

我们将对所有 3 的倍数做同样的事情。

下一个灰色的数字是 5，所以我们对所有 5 的倍数做同样的事情。

我们一直这样做，直到灰色数字的最小值小于或等于 sqrt(number)（在这种情况下，sqrt(120) 大约是 10.9544，向下取整是 10）。

您可能会问这如何实现。基本上，我们将创建一个布尔值数组，初始值全部为 false（灰色），然后对于从 2 到 sqrt(number) 的每个数字 i，我们将 i 的倍数标记为 true（彩色）。

上述算法称为“SieveOfEratosthenes”，它接收一个数字“number”作为参数，并返回一个大小为“number”的布尔指针数组“prime”，其中 prime[i] 的布尔值指示数字 i 是否为素数。该算法在下面定义。

bool * SieveOfEratosthenes(int number)
{
    bool * prime = new bool[number+1];
    for(int i=0;i<=number;i++)
        prime[i] = true;
    //0 and 1 are not prime, and we mark because we do not check in the algorithm
    //(because will cause bad results, if we divide by 0, we go to hell, and if we divide one by one, we will mark all numbers a nonprime.
    prime[0] = false;
    prime[1] = false;
    int squareRoot = sqrt(number);
    for(int i=2;i<=squareRoot;i++)
    {
        //If is gray (Is prime)
        if(prime[i])
        {
            //We start j by the next multiple of i (that is: 2*i), and we increase it by i each time until j is less than or equal to sqrt(number)
            for(int j=2*i;j<=number; j += i)
                prime[j] = false;
        }
    }
    return prime;
}

生成的数组是一个数组，如果 primes[i] 的值为 true，则 i 是素数。

此算法的使用示例在这里。

int main()
{
    int number = 30;
    bool * primes;
    primes = SieveOfEratosthenes(number);
    for(int i=0;i<number;i++)
    {
        if(primes[i])
            cout << i << " ";
    }
    return 0;
}
//Produces:
//2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113

结论

我们分析了如何优化算法，证明了我们的方法是有效的，并且比其他提出的算法执行的操作更少。

这就是全部内容，我希望这篇文章对您来说有趣和/或有帮助。我将开放新的素数测试优化算法。所以，如果您知道任何其他算法，请留言。