有没有一种简单的算法可以确定 X 是否为质数？

Question

有没有一种简单的算法可以确定 X 是否为质数？

algorithmprimes

29

我一直在尝试解决欧拉计划中的问题，并注意到其中一些问题要求你确定一个质数。

我知道可以将x除以2、3、4、5，......直到x的平方根，如果得到平方根，就可以（安全地）假设该数字是质数。不幸的是，这个解决方案似乎相当笨重。
我已经研究了更好的算法来确定一个数是否为质数，但很快就被搞糊涂了。

有没有简单的算法可以确定X是否为质数，而不会让普通程序员感到困惑?

非常感谢！

- Pulsehead

7

Project Euler的目的在于让你锻炼数学和编程能力，并持续进行研究和提高。 "寻常凡人"不是借口- Project Euler旨在帮助你克服这种限制！ - yfeldblum

1

我甚至认识一些在这些问题上也会晕倒的不死族。现在正是砍下他们的头并吞噬他们的灵魂的绝佳时机。 - Josh

16个回答

21

要生成小于某一限制值的所有质数，使用埃拉托色尼筛选法(该页面包含20种编程语言的变体)是最古老和最简单的解决方案。

在Python中：

def iprimes_upto(limit):
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

示例：

>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]

- J.F. Sebastian

OP说“不要让一个普通的程序员感到困惑？”。这个https://dev59.com/yXVC5IYBdhLWcg3woSpW 让我觉得yield确实很令人困惑。 - Koray Tugay

12

我看到Fermat素性检验已经被提出，但我一直在学习《计算机程序的构造和解释》，他们还提供了Miller-Rabin测试（见第1.2.6节，问题1.28）作为另一种选择。我已经成功地用它来解决欧拉计划的问题。

- Tim Whitcomb

1

我也在一些问题中使用了Miller-Rabin算法 +1。 - rslite

1

但我怀疑它是否比问题中建议的算法更快？你使用了随机化版本吗？ - vahidg

费马测试在卡迈克尔数上存在问题。 - Jason S

6

记住以下事实 (来自 MathsChallenge.net):

除2外，所有质数都是奇数。
大于3的所有质数都可以写成6k - 1或6k + 1的形式。
您不需要检查超过n的平方根。

这是我用于相对较小的n的C++函数:

bool isPrime(unsigned long n)
{
    if (n == 1) return false; // 1 is not prime
    if (n < 4) return true; // 2 and 3 are both prime
    if ((n % 2) == 0) return false; // exclude even numbers
    if (n < 9) return true; //we have already excluded 4, 6, and 8.
    if ((n % 3) == 0) return false; // exclude remaining multiples of 3

    unsigned long r = floor( sqrt(n) );
    unsigned long f = 5;
    while (f <= r)
    {
        if ((n % f) == 0)  return false;
        if ((n % (f + 2)) == 0) return false;
        f = f + 6;
    }
    return true; // (in all other cases)
}

你可能会想到更多的优化方式。

- Bill the Lizard

5

这里有一个简单的优化方法，虽然不是埃拉托斯特尼筛法，但非常易于实现：首先尝试将X除以2和3，然后循环j = 1..sqrt（X）/ 6，尝试将其除以6 * j-1和6 * j +1。这自动跳过了所有可被2或3整除的数字，使您获得了相当不错的加速效果。

- Jouni K. Seppänen

1

有一个更简单的选项：从5开始，每次增加2和4。效果是相同的，即基于（2,3）的轮子优化。请参见https://dev59.com/T3VC5IYBdhLWcg3wxEN1。 - jfs

3

我建议使用费马素性测试。它是一种概率性测试，但通常情况下都是正确的。而且与筛法相比，速度非常快。

- Michael L Perry

1

几乎是+1。问题在于费马测试对卡迈克尔数失效。 - Jason S

1

Miller-Rabin测试只是稍微困难一些，在维基百科上可以找到非常快的变体，可以确定地处理所有32位数字或n < 3 * 10^18。首先检查几个小质数的除法即可。 - gnasher729

@gnasher729 我知道这已经晚了大约4年，但是Miller-Rabin不是概率性的吗？或者你只是指在32位整数的相对较小样本空间中，它失败的几率非常低？我对数学不太擅长哈哈。 - adrian

2

对于相对较小的数字，使用x％n（其中n最多为sqrt（x））非常快速且易编写。以下是一些简单的改进方法：

仅测试2和奇数。

测试2、3以及6的倍数+或- 1（除了2或3之外的所有质数都是6的倍数+/- 1，因此您基本上只跳过了所有偶数和所有3的倍数）。

仅测试质数（需要计算或存储所有sqrt（x）以内的质数）。

您可以使用筛法来快速生成所有质数的列表，但它往往会占用大量内存。您可以使用6的倍数技巧将内存使用量减少到每个数字的1/3位。

我写了一个简单的素数类（C#），用于6的倍数+1和6的倍数-1的两个位域，然后进行简单的查找...如果我正在测试的数字超出筛子的范围，那么它就会回退到测试2、3和6的倍数+/- 1。我发现为大型筛子生成实际上比我目前解决的大多数欧拉问题即时计算质数要花更多时间。KISS原则再次发挥作用！

我编写了一个素数类，该类使用筛法预先计算较小的质数，然后依靠测试2、3和6的倍数+/- 1来测试筛子范围之外的数字。

- user17184

1

对于欧拉计划而言，拥有质数列表非常重要。我建议维护一个列表，您可以在每个问题中使用。

我认为你正在寻找的是埃拉托斯特尼筛法。

- Lucas Oman

1

我也在解决欧拉计划问题，实际上刚刚完成了编号为#3的问题，即查找复合数的最高质因数（?中的数字是600851475143）。

我查看了所有关于质数的信息（这里已经提到的筛法技术），以及维基百科上的整数分解，并想出了一个暴力试除算法，我认为这个算法可以做到。

因此，当我通过欧拉问题学习Ruby时，我正在研究编写我的算法，并偶然发现了mathn库，其中包含Prime类和Integer类的prime_division方法。多酷啊。我使用以下Ruby代码片段得到了正确的问题答案：

require "mathn.rb"
puts 600851475143.prime_division.last.first

这段代码将正确的答案输出到控制台。当然，在我发现这个小技巧之前，我做了很多阅读和学习，我想与大家分享一下...

- lil mudd

1

你说得对，最简单的方法是最慢的。你可以进行一些优化。

尝试使用模数代替平方根。跟踪你的质数。你只需要将7除以2、3和5，因为6是2和3的倍数，4是2的倍数。

Rslite提到了eranthenos筛法。它相当直接。我在家里有几种语言的代码。如果你想让我稍后发布这个代码，请添加评论。

这是我的C++版本。它还有很大的改进空间，但与动态语言版本相比，它运行速度快。

// Author: James J. Carman
// Project: Sieve of Eratosthenes
// Description: I take an array of 2 ... max values. Instead of removeing the non prime numbers,
// I mark them as 0, and ignoring them.
// More info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <iostream>

int main(void) {
        // using unsigned short.
        // maximum value is around 65000
        const unsigned short max = 50000;
        unsigned short x[max];
        for(unsigned short i = 0; i < max; i++)
                x[i] = i + 2;

        for(unsigned short outer = 0; outer < max; outer++) {
                if( x[outer] == 0)
                        continue;
                unsigned short item = x[outer];
                for(unsigned short multiplier = 2; (multiplier * item) < x[max - 1]; multiplier++) {
                        unsigned int searchvalue = item * multiplier;
                        unsigned int maxValue = max + 1;
                        for( unsigned short maxIndex = max - 1; maxIndex > 0; maxIndex--) {
                                if(x[maxIndex] != 0) {
                                        maxValue = x[maxIndex];
                                        break;
                                }
                        }
                        for(unsigned short searchindex = multiplier; searchindex < max; searchindex++) {
                                if( searchvalue > maxValue )
                                        break;
                                if( x[searchindex] == searchvalue ) {
                                        x[searchindex] = 0;
                                        break;
                                }
                        }
                }
        }
        for(unsigned short printindex = 0; printindex < max; printindex++) {
                if(x[printindex] != 0)
                        std::cout << x[printindex] << "\t";
        }
        return 0;
}

我会尽快找到它，然后分享我拥有的Perl和Python代码。它们风格相似，只是行数较少。

- J.J.

是的，这是一个轮子： http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.835 - nlucaroni

我在Stack Overflow上发布了一份用Python更简洁的版本。请查看我的答案。https://dev59.com/T3VC5IYBdhLWcg3wxEN1 - jfs

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rslite · Accepted Answer

第一个算法非常好，经常在Project Euler中使用。如果您知道所需的最大数值，还可以研究埃拉托色尼筛法。

如果您维护质数列表，也可以改进第一个算法，只需用质数除直到该数的平方根为止。

有了这两个算法（除法和筛法），您应该能够解决问题。

编辑：如评论中所述更正了名字。